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.

#include <bits/stdc++.h>
using namespace std;

struct
{
    int i , j;
}O[1001];

int find1(int n)
{
    for(int i = 0 ; i < n ; i++)
    {
        if(O[i].i > O[i].j) continue;
        int val = O[i].j - O[i].i;
        for(int j = i + 1 ; j < n && val >= 0 ; j++)
            val += (O[j].j - O[j].i);
        for(int j = 0 ; j < i && val >= 0 ; j++)
            val += (O[j].j - O[j].i);
        if(val >= 0) return i+1;
    }
    return -1;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> O[i].i >> O[i].j;
    cout << find1(n);
}