Salvadanaio
Problem
Vengono impostati il peso
E di un salvadanaio vuoto e il peso
F di un salvadanaio con monete. Il salvadanaio può contenere monete di tipo
N, per ogni tipo il valore
Pi e il peso
Wi< /sub> sono noti una moneta. Trova l'importo minimo e massimo di denaro che può essere nel salvadanaio.
Inserimento:
- la prima riga contiene i numeri
E e
F (
\(1<=E<=F<=10000\)< /span>);
- nel secondo - numero N (\(1<=N<=500\));
- nelle successive N righe - due numeri ciascuna, Pi e Wi < / codice>(\(1<=Pi<=50000\), \(1<=Wi<=10000\ ) ).
Tutti i numeri sono numeri interi.
Risultato: vengono visualizzati due numeri separati da uno spazio: le somme minima e massima. Se il salvadanaio non può avere esattamente il peso specificato, a condizione che sia riempito con monete del tipo specificato, stampa "Impossibile.".
Esempi
| # |
Input |
Uscita |
| 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
|
Questo è impossibile. |