A. Ayat and the film
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аят решил посмотреть какой-нибудь хороший фильм. Он взял пустую флешку, чтобы скопировать на нее фильм с лучшим рейтингом по версии AYAT FILM RATING. Выяснилось, что флешка не резиновая, и далеко не каждый фильм помещается на нее. Поэтому Аят решил выбрать фильм с лучшим рейтингом, который поместится на флешку. Какой фильм он из этого списка выбрал? Или Аят, взгрустнув по поводу несостоявшегося киносеанса, саботированного маленькой флешкой, пошел на пару физической культуры?

Входные данные

На первой строке целое число $$$S$$$ — размер флешки (от 1 до 30000). На второй строке целое число $$$N$$$ — количество фильмов в списке (от 1 до 100). Далее $$$N$$$ пар целых чисел: $$$R_i$$$ — рейтинг $$$i$$$-го фильма (от 1 до 100) и $$$V_i$$$ — размер $$$i$$$-го фильма (от 1 до 100000). Рейтинги у всех фильмов различны.

Выходные данные

Целое число $$$K$$$ — номер фильма с максимальным рейтингом, который помещается на флешке. Если Аят не смог выбрать фильм, выведите $$$-1$$$.

Примеры
Входные данные
1000
2
100 2000
50 4700
Выходные данные
-1
Входные данные
4000
5
100 4700
20 6200
50 1400
40 700
55 4200
Выходные данные
3