Last call cleared: hints, no solution

A city runs a fleet of identical ambulances, all free at minute 0. Calls are given in order of arrival: call i arrives at minute arrivals[i], and the list is sorted so arrivals never decrease. Handling call i keeps an ambulance busy for durations[i] minutes.

Calls are dealt with strictly in the given order. Each call is assigned to the ambulance that becomes free earliest (if several are free, any of them; the result is the same). The ambulance starts the call at the later of the call's arrival minute and the minute it became free, and is free again after the duration. Return the minute at which the last call is cleared, or 0 when there are no calls.

Examples

Input

ambulances = 2, arrivals = [0, 1, 2, 3], durations = [5, 2, 2, 2]

Output

7

Note

Call 0 runs 0-5, call 1 runs 1-3, call 2 runs 3-5 and call 3 runs 5-7.

Input

ambulances = 1, arrivals = [0, 0], durations = [3, 4]

Output

7

Note

With one ambulance the calls run back to back.

Constraints

• 1 <= ambulances <= 150000
• 0 <= number of calls <= 100000
• 0 <= arrivals[i] <= 100000, sorted ascending
• 1 <= durations[i] <= 1000

Hint 1: a nudge

When a new call arrives, which single number about each ambulance decides whether it can take the call, and which ambulance would you always prefer?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing