Caixa de dinheiro
Problem
O peso
E de um cofrinho vazio e o peso
F de um cofrinho com moedas são definidos. O cofrinho pode conter moedas de
N tipos, para cada tipo o valor
Pi e o peso
Wi< /sub> são conhecidos uma moeda. Encontre a quantia mínima e máxima de dinheiro que pode haver no cofrinho.
Entrada:
- a primeira linha contém os números
E e
F (
\(1<=E<=F<=10000\)< /span>);
- no segundo - número N (\(1<=N<=500\));
- nas próximas N linhas - dois números cada, Pi e Wi < / code>(\(1<=Pi<=50000\), \(1<=Wi<=10000\ ) ).
Todos os números são inteiros.
Saída: são exibidos dois números separados por um espaço - as somas mínima e máxima. Se o cofrinho não puder ter exatamente o peso especificado, desde que esteja cheio de moedas dos tipos especificados, imprima "Isto é impossível.".
Exemplos
| # |
Entrada |
Saída |
| 1 |
1000 1100
2
1 1
5 2
|
100 250 |
| 2 |
1000 1010
2
6 3
2 2
|
10 16 |
| 3 |
1000 2000
1
10 3
|
Isso é impossível. |