Задачи
Копилка
Копилка
Задан вес \textbf{E} пустой копилки и вес \textbf{F} копилки с монетами. В копилке могут находиться монеты \textbf{N} видов, для каждого вида известна ценность \textbf{P_i} и вес \textbf{W_i} одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
\InputFile
В первой строке находятся числа \textbf{E} и \textbf{F}, во второй - число \textbf{N}, в следующих \textbf{N} строках - по два числа, \textbf{P_i} и \textbf{W_i}. \textbf{1} ≤ \textbf{E} ≤ \textbf{F} ≤ \textbf{10000}, \textbf{1} ≤ \textbf{N} ≤ \textbf{500}, \textbf{1} ≤ \textbf{P_i} ≤ \textbf{50000}, \textbf{1} ≤ \textbf{W_i} ≤ \textbf{10 000}, все числа целые.
\OutputFile
Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "\textbf{This is impossible.}".
Входные данные #1
1000 1100 2 1 1 5 2
Выходные данные #1
100 250