Ring Road With a Small Tank

A ring road has n fuel stations numbered 0..n-1 in driving order; after station n-1 the road returns to station 0. A courier's van has a tank that holds at most capacity litres and starts empty.

Whenever the van is at station i it does two things, in this order:

1. Refuel: the tank becomes min(capacity, tank + gas[i]). Fuel that does not fit is lost.
2. Drive to station (i + 1) % n, which burns cost[i] litres. If the tank would go below 0, the van is stranded. Arriving with exactly 0 litres is fine.

A station s is a good start if the van can start at s with an empty tank and complete all n legs, arriving back at s. Return the number of good starts.

Examples

Input:  gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2], capacity = 100
Output: 1
Explanation: only station 3 works: tank after each leg is 3, 6, 4, 1, 0.

Input:  gas = [5, 0, 1], cost = [1, 1, 1], capacity = 3
Output: 2
Explanation: from station 0 the tank is capped at 3 (2 litres are lost), then
the legs leave 2, 1, 1 litres. From station 2 the legs leave 0, 2, 1.
Station 1 has no fuel for its first leg.

Constraints

• 1 <= n <= 10**5, len(gas) == len(cost) == n
• 0 <= gas[i], cost[i], capacity <= 10**9
• Target complexity: O(n) or O(n log n). Simulating from every start is far too slow.

Goals

• Simulate a fuel tank whose level is capped at every refill
• Count every valid starting point on a circular route, not just one
• Find an observation that avoids simulating from every start