Заправки на трассе Бишкек — Ош


Отправить решение Решать в редакторе

Сложность: 36%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Заправки на трассе Бишкек — Ош

На кольцевой трассе стоят n заправок. На i-й можно взять gᵢ литров, а до следующей заправки ехать cᵢ литров. Бак пуст, вместимость не ограничена. С какой заправки нужно начать, чтобы проехать полный круг? Если подходящих несколько, выведите наименьший номер; если нет ни одной — -1. Нумерация с 1.

Формат ввода

В первой строке n (1 ≤ n ≤ 10⁵). Далее n строк с gᵢ, cᵢ (0 ≤ gᵢ, cᵢ ≤ 10⁴).

Формат вывода

Номер заправки или -1.

Пример 1

Вход:

5
1 3
2 4
3 5
4 1
5 2

Выход:

4

Пример 2

Вход:

2
2 3
2 3

Выход:

-1

Комментарии

Еще нет ни одного комментария.