Олимпиадный тренинг

Задача . Копилка


Задача

Темы: Задача о рюкзаке
Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность Pi и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Входные данные
В первой строке находятся числа E и (1 <= E <= F <= 10000). Во второй - число (1<= N <= 500). В следующих N строках - по два числа, Pi и Wi (1 <= Pi <= 50000, 1 <= Wi <= 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.

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python92
С++ Mingw-w6450
Комментарий учителя