Problem
Das Gewicht des
E leeren Sparschwein- und das Gewicht des
F Münze-Sparschweins ist angegeben. Im Sparschwein können sich
N -Arten befinden, für jede Art ist der Wert von
Pi und das Gewicht von
Wi einer Münze bekannt. Finden Sie die minimalen und maximalen Geldbeträge, die sich in einem Sparschwein befinden können.
Eingabe:
- in der ersten Zeile befinden sich die Zahlen
E und
F (
\(1<=E<=F<=10000\));
- die zweite ist die Zahl
N (
\(1<=N<=500\));
-die folgenden
N Zeilen enthalten jeweils zwei Zahlen,
Pi und
Wi (
\(1<=Pi<=50000\),
\(1<=Wi<=10000\)).
Alle Zahlen sind ganze Zahlen.
Ausgabe: zwei Zahlen werden durch ein Leerzeichen ausgegeben - die minimalen und maximalen Summen. Wenn das Sparschwein kein genau festgelegtes Gewicht haben kann, vorausgesetzt, es ist mit Münzen bestimmter Arten gefüllt, - ziehen Sie das "
This is impossible.".
Beispiele
| № |
Eingabe |
Ausgabe |
| 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
|
This is impossible. |