eolymp
bolt
Try our new interface for solving problems
Problems

Moneybox

Moneybox

Time limit 2 seconds
Memory limit 64 MiB

Given the weight of E is empty piggy banks and weight F piggy bank with coins. In the piggy bank may be the coin of N, for each known value of P_i and the weight W_i of a coin. Find the minimum and maximum amount of money that may be in the kitty.

Input data

In the first row are the number of E and F, the second - the number N, the following N lines - two numbers, P_i and W_i. 1EF10000, 1N500, 1P_i50000, 1W_i10 000, all numbers are integers.

Output data

Two numbers are derived through the gap - minimum and maximum amounts. If the piggy bank may not have exactly the specified weight, provided that it is filled with coins given species - print "This is impossible.".

Examples

Input example #1
1000 1100
2
1 1
5 2
Output example #1
100 250