Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность Pi и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Входные данные
В первой строке находятся числа E и F, во второй - число N, в следующих N строках - по два числа, Pi и Wi.
1<=E<=F<=10000, 1<=N<=500, 1<=P
i<=50000, 1<=W
i<=10000, все числа целые.
Выходные данные
Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".
|
Ввод |
Вывод |
|
1000 1100
2
1 1
5 2
|
100 250 |
|
1000 1010
2
6 3
2 2
|
10 16 |
|
1000 2000
1
10 3
|
This is impossible. |