Rezolvare PBinfo #552

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.