Меньшиков: Условия задач

Задан вес \(E\) пустой копилки и вес \(F\) копилки с монетами. В копилке могут находиться монеты \(N\) видов, для каждого вида известна ценность \(P_i\) и вес \(W_i\) одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Ограничения

\(1 \le E\le F\le 10000\), \(1 \le N \le 500\), \(1\le P_i\le 50000\), \(1\le W_i \le 10000\), все числа целые.

Формат входных данных

В первой строке находятся числа \(E\) и \(F\), во второй - число \(N\), в следующих \(N\) строках - по два числа, \(P_i\) и \(W_i\).

Формат выходных данных

Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".

Примеры

1000 1100
2
1 1
5 2

100 250

1000 1010
2
6 3
2 2

10 16

1000 2000
1
10 3

This is impossible.