Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

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

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

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


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: