Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Автор: Фёдор Меньшиков, ВГПУ.
Difficulty Gamma
Moneybox
Russian
Given an empty box of weight E and a box filled with
coins of weight F. The box may contain N types of
coins. For each coin we know the price P and the
weight W.
Find the minimum and maximum amount of money that
may be in the box.
Input
The first line contains the number E and F, the second
line the number N and the following N lines - two numbers,
Pi and Wi.
Output
Print two numbers separated by a space - minimum and maximum
amounts.
If the box cannot have the exact target weight, provided
that it is filled with given coins -print
"This is impossible.".
Limitations
1 ≤ E ≤ F ≤ 10 000; 1 ≤ N ≤ 500;
1 ≤ Pi ≤ 50 000;
1 ≤ Wi ≤ 10 000.
|
Input 1
|
Input 2
|
Input 3
|
1000 1100
2
1 1
5 2
|
1000 1010
2
6 3
2 2
|
1000 2000
1
10 3
|
|
Output 1
|
Output 2
|
Output 3
|
100 250
|
10 16
|
This is impossible.
|
Для отправки решений необходимо выполнить вход.
|