Задача
Задан вес
E пустой копилки и вес
F копилки с монетами. В копилке могут находиться монеты
N видов, для каждого вида известна ценность
Pi и вес
Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Входные данные
В первой строке находятся числа
E и
F (1 <= E <= F <= 10000). Во второй - число
N (1<= N <= 500). В следующих
N строках - по два числа,
Pi и
Wi (1 <= P
i <= 50000, 1 <= W
i <= 10000). Все числа целые.
Выходные данные
Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "
This is impossible.".
Примеры
| № | Входные данные | Выходные данные |
|
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.
|