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

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


Задача

Темы: Задача о рюкзаке
Задан вес 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.