Скарбничка

Задано вагу E пустої скарбнички та її F з монетами. У скарбничці можуть знаходитись монети N видів, для кожного виду відома цінність P_i і вага W_i однієї монети. Знайти мінімальну і максимальну суми грошей, які можуть знаходитись у скарбничці.

Вхідні дані

У першому рядкуе знаходяться числа E і F, у другому - число N, у наступних N рядках - по два числа, P_i и W_i. 1 ≤ E ≤ F ≤ 10000, 1 ≤ N ≤ 500, 1 ≤ P_i ≤ 50000, 1 ≤ W_i ≤ 10 000, всі числа цілі.

Вихідні дані

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

Приклади