Cerința
În ţara lui Gigel se află n
oraşe, numerotate de la 1
la n
, cu proprietatea că din oraşul i
exista drum numai spre oraşul i+1
, iar din oraşul n
există drum spre oraşul 1
. Gigel doreşte să viziteze toate cel n
oraşe în ordine, pornind dintr-un oraş oarecare şi întorcându-se la final în acesta.
Lucrurile nu sunt atât de simple, deoarece pentru a se deplasa dintr-un oraş i
în oraşul următor Gigel are nevoie de o cantitate cunoscută de energie, A[i]
. De asemenea, în fiecare oraş Gigel acumulează o cantitate cunoscută de energie B[i]
, pe care o poate folosi pentru a se deplasa mai departe. Iniţial, Gigel nu are deloc energie.
Determinaţi, dacă există, un oraş din care Gigel poate începe vizitarea celor n
oraşe, astfel încât la final Gigel să se întoarcă în oraşul din care a plecat.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi n
perechi de numere naturale A[i] B[i]
.
Date de ieșire
Programul va afișa pe ecran numărul P
, reprezentând numărul de ordine al oraşului din care poate porni Gigel, respectiv -1
dacă drumul nu poate fi parcurs, indiferent din care oraş ar pleca.
Restricții și precizări
1 ≤ n ≤ 1000
1 ≤ A[i] ≤ 1000
0 ≤ B[i] ≤ 1000
- Dacă Gigel poate pleca din mai multe oraşe, se va afişa oraşul cu numărul de ordine mai mic
- Dacă energia necesară pentru deplasarea dintr-un oraş în următorul este egală cu energia pe care o are Gigel la plecarea din oraş, deplasarea se poate face.
Exemplu
Intrare
5 6 7 8 4 2 6 1 4 2 1
Ieșire
3
Explicație
Gigel poate pleca din oraşul 3
sau din oraşul 4
.