|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Фёдор Меньшиков, ВГПУ.
Сложность Гамма
Копилка
English
Задан вес E пустой копилки и вес F копилки с монетами. В копилке
могут находиться монеты N видов, для каждого вида известна ценность
Pi и вес Wi одной монеты.
Найти минимальную и максимальную суммы денег, которые могут находиться
в копилке.
Ввод
В первой строке находятся числа E и F, во второй - число N,
в следующих N строках - по два числа, Pi и
Wi.
Вывод
Выводятся два числа через пробел - минимальная и максимальная суммы.
Если копилка не может иметь точно заданный вес при условии,
что она наполнена монетами заданных видов, -
вывести "This is impossible.".
Ограничения
1 ≤ E ≤ F ≤ 10 000; 1 ≤ N ≤ 500;
1 ≤ Pi ≤ 50 000;
1 ≤ Wi ≤ 10 000.
|
Ввод 1
|
Ввод 2
|
Ввод 3
|
1000 1100
2
1 1
5 2
|
1000 1010
2
6 3
2 2
|
1000 2000
1
10 3
|
|
Вывод 1
|
Вывод 2
|
Вывод 3
|
100 250
|
10 16
|
This is impossible.
|
Для отправки решений необходимо выполнить вход.
|