A circular toll loop has n gates numbered 0 to n-1 in the order a vehicle passes them. At gate i the vehicle receives credit_i currency, and then must pay cost_i to travel to the next gate (gate (i+1) mod n). A vehicle starts at some gate with a balance of 0, collects that gate's credit, pays to move to the next gate, collects the next gate's credit, pays again, and so on until it has visited all n gates exactly once and returned to its starting gate. The balance must never go negative at any point after a payment.
Find the smallest starting gate index (0-indexed) from which the full loop can be completed. If no starting gate allows completing the full loop, print -1.
Input format
Line 1: an integer n.
Line 2: n space-separated integers credit_0 ... credit_{n-1}.
Line 3: n space-separated integers cost_0 ... cost_{n-1}.
Output format
A single integer: the smallest valid starting gate index, or -1 if none exists.
Constraints
- 1 <= n <= 40
- 0 <= credit_i, cost_i <= 50