SPOJ Brasil

O conceito de computação em nuvem tem se tornado muito popular nos últimos tempos. Um dos principais tipos de computação em nuvem é conhecido como IaaS (Infrastructure as a Service, em português Infraestrutura como Serviço), onde provedores disponibilizam servidores que podem ser alugados e gerenciados pela Internet.

A Cloud, Inc. é uma empresa que disponibiliza serviços de IaaS. Ela está projetando um novo data center para atender a seus clientes. Através de uma pesquisa, eles descobriram que seus clientes, como um todo, precisam de K servidores, cada um dos quais precisa ser capaz de suportar um certo nível de demanda. Se supormos que o custo de um servidor sempre cresce à medida que a demanda que aquele servidor deve suportar cresce, a melhor solução em termos de custo é comprar K servidores que sejam cada um explicitamente montados de forma a atender exatamente à demanda necessária.

Porém, ter K configurações diferentes de hardware no data center é extremamente problemático para os administradores de sistema. Para simplificar a administração, eles exigem que sejam comprados não mais do que L tipos diferentes de servidor. Um servidor que suporta uma certa demanda c também suporta qualquer demanda menor que c.

Uma solução possível é comprar apenas um tipo de servidor, que seja capaz de atender à maior demanda necessária, pois ele também será capaz de atender a todas as outras demandas. Porém, o custo dessa solução pode ser proibitivo. Considerando que você pode comprar até L tipos diferentes de servidor, provavelmente há uma solução melhor. Por exemplo, suponha que haja 3 clientes, com demandas 3, 7 e 16. Suponha que o custo de um servidor que suporta uma demanda até 3 é R$ 1.500, o custo de um servidor que suporta demanda 7 é R$ 5.500 e o custo de um servidor que suporta demanda 16 é de R$ 19.200. Se você quer comprar até 2 tipos de servidor para atender aos 3 clientes, há quatro opções:

• Comprar três servidores de capacidade 16, a um custo total de R$ 57.600;
• Comprar dois servidores de capacidade 16 e um servidor de capacidade 7, a um custo total de R$ 43.900;
• Comprar dois servidores de capacidade 16 e um servidor de capacidade 3, a um custo total de R$ 39.900;
• Comprar um servidor de capacidade 16 e dois servidores de capacidade 7, a um custo total de R$ 30.200.

Dentre essas opções, a que apresenta o menor custo é a última.

Você receberá uma lista de K demandas requisitadas e o preço de um servidor que suporta cada uma dessas demandas. Determine o menor preço total para comprar K servidores de forma tal que seja possível atingir a demanda requisitada e sejam comprados servidores de no máximo L tipos diferentes.

Observações

• Cada servidor atende a um e apenas um cliente. Um servidor de capacidade 4 não pode atender simultaneamente a dois clientes com demanda 2 cada.
• Sejam D_i e D_j duas demandas, e P_i e P_j os preços associados a servidores que sejam capazes de suprir essas demandas. Se D_i < D_j, então P_i ≤ P_j.

Entrada

Há vários casos de teste.

Cada caso de teste começa com uma linha contendo dois inteiros K e L, respectivamente o número de servidores requisitados e o número máximo de tipos de servidor a serem comprados (1 ≤ L ≤ K ≤ 500). Em seguida, há K linhas, cada uma das quais contendo dois inteiros D e P, respectivamente a demanda necessária e o menor preço de um servidor que é capaz de atender àquela demanda (1 ≤ D ≤ 1000, 1 ≤ P ≤ 100.000). Se houver mais de uma linha com o mesmo valor de D, então essas linhas também terão mesmo valor de P.

A entrada termina com K = L = 0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma linha contendo um inteiro T, que representa o menor custo total que pode ser obtido.

Exemplos

Entrada:
10 3
1 1
2 4
3 5
4 7
5 8
6 12
7 13
8 18
9 19
10 21
0 0

Saída:
129

A melhor opção para comprar servidores de 3 tipos que atendam às dez demandas requisitadas é comprar:

• 3 servidores que suportam demanda 10, que vão cobrir os casos de demanda 10, 9 e 8;
• 2 servidores que suportam demanda 7, que vão cobrir os casos de demanda 7 e 6;
• 5 servidores que suportam demanda 5, que vão cobrir os demais casos.

O custo total é 3*21 + 2*13 + 5*8 = 129.