Аят решил посмотреть какой-нибудь хороший фильм. Он взял пустую флешку, чтобы скопировать на нее фильм с лучшим рейтингом по версии 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
