Идет сильный дождь. Но Сервалу сегодня исполнилось 3 года, и это его первый день, когда он должен пойти в детский сад! К сожалению, он живет далеко от детского сада, а его отец слишком занят, чтобы отвезти его туда. Единственный выбор для этого бедного маленького мальчика в этот дождливый день — ждать автобуса. При таких обстоятельствах Сервал воспользуется первым попавшимся автобусом, куда бы он ни поехал. Если одновременно придет несколько автобусов, он выберет любой из них случайно.
Сервал придет на автобусную остановку во время \(t\), через эту автобусную остановку проходят \(n\) автобусных маршрутов. Первый автобус \(i\)-го маршрута приходит в момент времени \(s_i\) минут, а каждый следующий автобус этого маршрута приходит на \(d_i\) минут позже предыдущего.
Вы — лучший друг Сервала, и вы хотите узнать, на какой автобус он сядет. Если одновременно приходит несколько автобусов, вы можете вывести любой из них.
Выходные данные
Выведите одно число — номер автобуса, на который сядет Сервал. Если есть несколько возможных ответов, вы можете вывести любой.
Примечание
В первом примере первый автобус первого маршрута приходит во время \(6\), а автобус второго маршрута приходит во время \(9\), поэтому ответом является первый маршрут.
Во втором примере третий автобус приходит во время \(5\), поэтому это и есть ответ.
В третьем примере автобусы первого маршрута приходят во времена \(2\), \(4\), \(6\), \(8\) и так далее, автобусы второго маршрута приходят во времена \(2\), \(5\), \(8\) и так далее, автобусы третьего маршрута приходят во времена \(2\), \(6\), \(10\) и так далее, поэтому \(1\) и \(2\) являются правильными ответами, а \(3\) — нет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
6 4
9 5
|
1
|
|
2
|
5 5
3 3
2 5
5 6
4 9
6 1
|
3
|
|
3
|
3 7
2 2
2 3
2 4
|
1
|