Задачі
Скарбничка
Скарбничка
Задано вагу \textbf{E} пустої скарбнички та її \textbf{F} з монетами. У скарбничці можуть знаходитись монети \textbf{N} видів, для кожного виду відома цінність \textbf{P_i} і вага \textbf{W_i} однієї монети. Знайти мінімальну і максимальну суми грошей, які можуть знаходитись у скарбничці.
\InputFile
У першому рядкуе знаходяться числа \textbf{E} і \textbf{F}, у другому - число \textbf{N}, у наступних \textbf{N} рядках - по два числа, \textbf{P_i} и \textbf{W_i}. \textbf{1} ≤ \textbf{E} ≤ \textbf{F} ≤ \textbf{10000}, \textbf{1} ≤ \textbf{N} ≤ \textbf{500}, \textbf{1} ≤ \textbf{P_i} ≤ \textbf{50000}, \textbf{1} ≤ \textbf{W_i} ≤ \textbf{10 000}, всі числа цілі.
\OutputFile
Виводяться два числа через пропуск - мінімальна і максимальна суми. Якщо скарбничка не може мати точно задану вагу при умові, що вона наповнена монетами заданих видів, - вивести "\textbf{This is impossible.}".
Вхідні дані #1
1000 1100 2 1 1 5 2
Вихідні дані #1
100 250