Moneybox#844
Given the weight of an empty piggy bank and the weight of the piggy bank with coins. The piggy bank may contain coins of types, for each type, the value P_i and weight W_i of a coin are known. Find the minimum and maximum amount of money that may be in the piggy bank.
The first line contains the numbers and , the second line contains the number , the following lines - two numbers, P_i and W_i. 1 \leq E \leq F \leq 10000, 1 \leq N \leq 500, 1 \leq P_i \leq 50000, 1 \leq W_i \leq 10000, all numbers are integers.
Output two numbers separated by a space - minimum and maximum amounts. If the piggy bank may not have exactly the specified weight, provided that it is filled with coins of the given types - print "This is impossible.".
Пример 1