All problems

Mountain Pass Thaw

Medium · binary search

A mountain road is blocked by several patches of snow. Patch i is snow[i] centimetres deep today, and every day the sun melts melt[i] centimetres of it. A patch cannot get shallower than nothing: once it has melted away it stays at 0, so after d days its depth is max(0, snow[i] - melt[i] * d).

The road authority has a snow blower that can clear the road in one go as long as the total depth of all the patches (added together) is at most allowed centimetres. The first day is day 0 (today), and nothing melts until day 1.

Return the earliest day on which the total depth is at most allowed.

Examples

Example 1

Input: snow = [8, 5, 3], melt = [2, 1, 1], allowed = 4

Output: 3

The total depth over the first days is 16, 12, 8 and then 4 on day 3 (patches of 2, 2 and 0 centimetres). Day 3 is the first day it is at most 4.

Example 2

Input: snow = [3, 3], melt = [1, 1], allowed = 10

Output: 0

Today's total is 6, which the blower can already handle.

Constraints