Недавно Ваня накопил $$$k$$$ монет и теперь хочет потратить их на покупку тетрадок в клеточку. Ему известна информация про $$$n$$$ магазинов: а именно, ему известно $$$n$$$ пар чисел ($$$a_i$$$, $$$b_i$$$), где $$$a_i$$$ означает цену тетрадки в клеточку в $$$i$$$-м магазине, а $$$b_i$$$ означает количество тетрадей в клеточку, имеющихся в наличии в этом магазине.
Какое максимальное число тетрадей в клеточку может купить Ваня?
В первой строке записаны целые числа $$$k$$$ и $$$n$$$ ($$$1 \leq k \leq 10^{18}$$$, $$$1 \leq n \leq 10^5$$$).
В следующих $$$n$$$ строках записано по два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \leq a_i, b_i \leq 10^6$$$).
Выведите одно число – наибольшее количество тетрадей в клеточку, которое может купить Ваня.
10 2 1 5 2 5
7
15 1 5 2
2
20 3 10 1 2 4 5 6
6
| MSPU Training Contest 2018-2019 |
|---|
| Finished |
