Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N−1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump.

Initially, you have a tank of infinite capacity carrying no petrol. You can start the tour at any of the petrol pumps. Calculate the first point from where the truck will be able to complete the circle. Consider that the truck will stop at each of the petrol pumps. The truck will move one kilometer for each litre of the petrol.

Input Format

The first line will contain the value of N.
The next N lines will contain a pair of integers each, i.e. the amount of petrol that petrol pump will give and the distance between that petrol pump and the next petrol pump.

Constraints:
1≤N≤105
1≤amount of petrol, distance≤109

Output Format

An integer which will be the smallest index of the petrol pump from which we can start the tour.

Sample Input

3
1 5
10 3
3 4

Sample Output

1

Explanation

We can start the tour from the second petrol pump.

Copyright © 2015 HackerRank.

Consider the amount of fuel you have in your tank as a function of the amount of stations you have passed (the integral of the change in fuel {gained - used} per station results in the amount of fuel for every station, the fundamental theorem of calculus). Now: this function has to be positive for every station because you cannot ever have negative fuel in your tank. This only happens whenever you start at a global minimum of this function. You are essentially shifting the function vertically, setting it to zero at your starting point and if this is the lowest point then all other points will be positive. 

This is assuming that a full circle will not result in a net fuel loss (then you cannot complete the circle) and furthermore that there are no more than 1 global minima (then you get stuck with exactly 0 fuel at the position of the second global minimum).

Code

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int n, p[100005], d[100005];

int main() {

    scanf("%d", &n);

    for (int i = 0; i < n; ++i) scanf("%d%d", &p[i], &d[i]);

    int ret = 0, amount = 0, sum = 0;

    for (int i = 0; i < n; ++i) {

        p[i] -= d[i];

        sum += p[i];

        if (amount + p[i] < 0) {

            amount = 0;

            ret = i + 1;

            cout<<"setting res at pos  "<<i<<" as "<<i+1<<endl;

        } else amount += p[i];

    }

    printf("%d\n", sum >= 0 ? ret : -1);

    return 0;

}