Problema A - Mergulho lucrativo

O Filipe é caçador de tesouros mundialmente famoso. Corajoso e calculista, não se deixa intimidar pela dificuldade do desafio, mas continua a ter de prestar contas à organização que patrocina as suas expedições, a Organização de Náuticos e Investigadores. Recentemente, decidiu virar a sua atenção para o famoso Triângulo das Bermudas. Ele pensou "À quantidade de barcos que por ali se afundam, o fundo do mar deve estar cheio de relíquias por descobrir".

Ao estudar os mapas, descobriu que o fundo do mar é quase perfeitamente estratificado, ao estilo das igualmente famosas Vinhas do Douro. Assim o fundo do mar pode ser visto como uma "escada", em que a primeira plataforma tem uma unidade de profundidade, a segunda tem duas, etc.

Depois de muito estudar, o Filipe conseguiu localizar um conjunto de N tesouros, cada um representado pela profundidade Pi a que se encontra e o seu valor monetário Vi. Cada tesouro encontra-se numa só plataforma, podendo haver vários tesouros na mesma plataforma.

Para carregar os tesouros, vai ser descida uma arca com capacidade para transportar K tesouros (sendo que o Filipe não consegue levar tesouro nenhum sozinho). O movimento da arca custa C euros por cada unidade de profundidade que tem de fazer até chegar ao ponto mais fundo. Depois de estar instalada, o Filipe pode apanhar qualquer tesouro que esteja nessa plataforma ou em plataformas superiores a ela, enquanto a arca não estiver cheia. Quando estiver carregada ou não houver mais tesouros para apanhar, a arca é subida e termina a aventura.

Ok, tudo planeado, falta o financiamento. A O.N.I. quer saber qual é o lucro máximo que podem ter com esta expedição, isto é, a soma dos valores dos tesouros apanhados menos os custos de manuseamento da arca. É aí que tu entras.

Imagina por um exemplo um caso com C=2 (custo de 2 por cada unidade de profundidade), K=3 (arca com capacidade para 3 tesouros) e N=5 (5 tesouros), com a localização e valor dostesouros ilustrada na figura seguinte:

Exemplo

Neste caso a solução ótima seria apanhar apenas os 3 primeiros tesouros, baixando a rede até à profundidade 4. O lucro seria (4+1+8)-(4*2) = 5

O Problema

Dado o custo de manuseamento por unidade de profundidade C, a capacidade K da arca e um conjunto de N tesouros, calcular o maior lucro que é possível obter (soma dos valores dos tesouros menos o custo total do manuseamento da arca).

Input

A primeira linha contém três inteiros, C, representando o custo por unidade de profundidade, K, representando a capacidade da arca e N, o número de tesouros.

Seguem-se N linhas, cada uma contendo dois inteiros: a profundidade Pi a que o i-ésimo tesouro se encontra e o seu respetivo valor Vi.

Output

O output deve conter uma única linha com um inteiro que representa o lucro máximo que a expedição pode render.

Nota: o valor do lucro é menor que 2^60.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ N ≤ 100 000       Número de tesouros
1 ≤ K ≤ N       Capacidade da arca
1 ≤ Pi ≤ 1 000 000 000       Profundidade dos tesouros

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Grupo Número de Pontos Restrições adicionais
1 10 N ≤ 20 , Pi ≤ 1000
2 20 N ≤ 1000 , Pi ≤ 1 000 000
3 30 Pi ≤ 10 000
4 40 -

Input do Exemplo 1

2 3 5
3 1
1 4
8 5
4 8
8 6

Output do Exemplo 1

5

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

2 4 5
3 1
1 4
8 5
4 8
8 6

Output do Exemplo 2

7

Explicação do Exemplo 2

Aqui, ao contrário do exemplo anterior, é vantajoso descer a arca até à plataforma de profundidade 8, de forma a apanhar os tesouros desse nível e da primeira e da quarta plataforma, prefazendo assim um lucro de (5+6+4+8)-(2*8) = 7.


Prova de Seleção das ONI'2018
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(10 de junho de 2018)