Гриб Филиппов приготовил себе покушать, а за едой решил посмотреть видео на TubeTube. Он может выделить на обед не более \(t\) секунд, поэтому просит вас помочь с выбором видео.
Лента TubeTube представляет собой список из \(n\) видео, пронумерованных от \(1\) до \(n\); \(i\)-е видео длится \(a_i\) секунд и имеет интересность \(b_i\). Изначально лента открыта на первом видео, за \(1\) секунду Гриб может пропустить видео и перейти к следующему (если следующее существует). Переходить к следующему видео Гриб может любое количество раз (в том числе и ноль).
Помогите Грибу выбрать одно видео, которое он сможет открыть и посмотреть за \(t\) секунд. Если таких несколько, он хочет выбрать наиболее интересное. Выведите номер подходящего видео, или \(-1\), если таких нет.
Выходные данные
Выведите \(q\) целых чисел, каждое из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите номер самого интересного видео, которое успеет посмотреть Гриб. Если ответов несколько — выведите любой. Выведите \(-1\), если он не успеет посмотреть ни одно видео до конца обеда.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 9
1 5 7 6 6
3 4 7 1 9
4 4
4 3 3 2
1 2 3 4
5 7
5 5 5 5 5
2 1 3 9 7
4 33
54 71 69 96
42 24 99 1
2 179
55 66
77 88
|
3
2
3
-1
2
|