First Stockout Day

Difficulty: 1000 3000 ms 128 MB

implementation

A warehouse starts with S items; day i ships d_i items. Print the first day the warehouse cannot fulfil demand (stock would go negative), or −1 if it never runs out.

Input: the first line has N and S; the second line has the N daily demands.

Output: the first stockout day (1-based), or −1.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ S ≤ 10⁶
• 0 ≤ d_i ≤ 60

Sample Tests

4 100
30 30 30 30

4

2 5
2 3

-1

Read the Editorial