В игровом шоу «Десять слов мудрости» участвуют \(n\) участников, пронумерованных от \(1\) до \(n\), каждый из которых даёт один ответ. \(i\)-й ответ состоит из \(a_i\) слов и имеет качество \(b_i\). Никакие два ответа не имеют одинакового качества, и по крайней мере один ответ имеет длину не более \(10\) слов.
Победителем шоу становится ответ с наивысшим качеством из всех ответов, которые не превышают \(10\) слов. Какой ответ станет победителем?
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую одно целое число \(x\) (\(1 \leq x \leq n\)) — победителя шоу, согласно правилам, указанным в условии.
Можно показать, что согласно ограничениям в условии, для каждого теста существует ровно один победитель.
Примечание
В первом тесте предоставлены следующие ответы:
- Ответ 1: \(7\) слов, качество \(2\)
- Ответ 2: \(12\) слов, качество \(5\)
- Ответ 3: \(9\) слов, качество \(3\)
- Ответ 4: \(9\) слов, качество \(4\)
- Ответ 5: \(10\) слов, качество \(1\)
Мы видим, что ответы с индексами \(1\), \(3\), \(4\) и \(5\) имеют длину, не превышающую \(10\) слов. Из этих ответов победителем является тот, у которого наивысшее качество.
Сравнивая качества, мы находим, что:
- Ответ 1 имеет качество \(2\).
- Ответ 3 имеет качество \(3\).
- Ответ 4 имеет качество \(4\).
- Ответ 5 имеет качество \(1\).
Среди этих ответов, победителем является Ответ 4 с наивысшим качеством.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
7 2
12 5
9 3
9 4
10 1
3
1 2
3 4
5 6
1
1 43
|
4
3
1
|