The weight
E of an empty piggy bank and the weight
F of a piggy bank with coins are set. The piggy bank can contain coins of
N types, for each type the value
Pi and the weight
Wi are known one coin. Find the minimum and maximum amount of money that can be in the piggy bank.
Input:
- the first line contains numbers
E and
F (
\(1<=E<=F<=10000\)< /span>);
- in the second - number N (\(1<=N<=500\));
- in the next N lines - two numbers each, Pi and Wi (\(1<=Pi<=50000\), \(1<=Wi<=10000\) ).
All numbers are integers.
Output: two numbers separated by a space are displayed - the minimum and maximum sums. If the piggy bank cannot have exactly the specified weight, provided that it is filled with coins of the specified types, print "This is impossible.".
Examples
| # |
Input |
Output |
| 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. |