SPOJ Brasil

Paulo trabalha para uma grande empresa chamada Ábaco Computadores e Manutenções (ACM). O seu trabalho é prover manutenção de computadores de clientes da ACM, localizados em diversas partes do país. Por esta razão, Paulo normalmente passa um bom número de horas por semana dentro de aviões. Obviamente, Paulo sempre carrega consigo o seu laptop, de forma que mesmo quando está viajando de avião pode executar muitas tarefas relacionadas a seu trabalho.

Como as baterias de laptops geralmente não duram muito, Paulo tem estudado alternativas para aumentar o tempo de duração da bateria durante vôos. Ele descobriu que processadores modernos podem operar a diversos níveis de freqüência, oferecendo um compromisso entre desempenho e consumo de energia. A idéia inicial de Paulo foi simplesmente configurar o seu laptop na freqüência mais baixa. No entanto, ele notou que isso não era muito útil, já que as tarefas executavam muito lentamente no laptop, e não haveria tempo de executar todas as tarefas, de forma que a energia restante na bateria seria inútil.

Paulo notou, entretanto, que a influência do nível freqüência no desempenho varia de aplicação para aplicação, dependendo se elas são limitadas por memória, CPU ou E/S. Adicionalmente, como processadores modernos permitem que o nível de freqüência seja alterado por software, Paulo planeja utilizar esse mecanismo para aumentar o tempo de uso da bateria de seu laptop, de forma ainda a manter um desempenho razoável. Para levar em consideração tanto a energia como o desempenho, Paulo decidiu usar uma métrica já bem conhecida, denominada Produto Energia × Tempo (mais conhecida pelo acrônimo em inglês, EDP, Energy × Delay Product).

Paulo tem uma lista de programas que devem ser executados seqüencialmente, e todas as informações sobre o tempo e a energia necessários para executar cada programa em cada nível de freqüência, além da informação de quanta energia é gasta para fazer o processador mudar de freqüência. No entanto, para testar sua nova idéia, Paulo ainda tem um problema: como a maioria dos administradores de sistema, ele não gosta de programar. Ele está pedindo a sua ajuda, já que você é um grande amigo e um expert em algoritmos e programação, para determinar o nível de freqüência em que cada um de seus programas deve ser executado de forma a minimizar o EDP total.

Entrada

A entrada contém vários casos de testes. A primeira linha de um caso de teste contém quatro inteiros F, P, E, e A, identificando respectivamente o número de níveis de freqüência suportados pelo processador do laptop de Paulo (1 ≤ F ≤ 20), o número de programas a serem executados seqüencialmente (1 ≤ P ≤ 5000), a energia necessária, em Joules, para trocar entre dois quaisquer níveis de freqüência (1 ≤ E ≤ 100) e o tempo (em ms) para trocar entre quaisquer dois níveis de freqüência (1 ≤ A ≤ 100). Os níveis de freqüência são identificados por inteiros de 1 a F, e os programas são identificados por inteiros de 1 a P.

As P × F linhas seguintes descrevem os programas, com F linhas para cada programa (as primeiras F linhas correspondem ao programa 1, as próximas F linhas correspondem ao programa 2, e assim por diante). A f-ésima linha correspondente ao programa p contém dois números E_p,f e A_p,f, representando respectivamente a quantidade de energia (em Joules) e tempo (em ms) para executar o programa p no nível de freqüência f (1 ≤ E_p,f ≤ 1000 e 1 ≤ A_p,f ≤ 1000). No início de cada caso de teste o processador está no nível 1 de freqüência. O final da entrada é indicada por F = P = E = A = 0.

Saída

Para cada caso de teste da entrada, seu programa deve produzir uma linha na saída, contendo o EDP mínimo para executar seqüencialmente o conjunto de programas de 1 a P (ou seja, na ordem em que aparecem na entrada).

Exemplo de entrada

2 3 10 10
50 120
100 90
500 600
600 500
400 1000
500 700
3 3 2 5
7 10
8 5
15 4
12 4
11 5
12 4
7 10
8 5
15 4
0 0 0 0

Saída para o exemplo de entrada

656100
145