20. Cruise Party Guests

Difficulty: easy · Array, Prefix Sum

Problem

A party on a cruise ship runs for `T` hours. During hour `i` (1-based), `E[i]` guests enter and then `L[i]` guests leave. The ship starts empty. After each hour, the number of guests on board is the previous count plus `E[i]` minus `L[i]`. Find the maximum number of guests on board at the end of any hour.

Input

- Line 1: the integer `T`. - Line 2: `T` space-separated integers `E[1] ... E[T]`. - Line 3: `T` space-separated integers `L[1] ... L[T]`.

Output

Print the maximum number of guests present after any hour.

Example 1

Input:
5
7 0 5 1 3
1 2 1 3 4
Output:
8

Explanation: Counts after each hour are 6, 4, 8, 6, 5; the maximum is 8 (after hour 3).

Example 2

Input:
4
3 5 2 0
0 2 4 4
Output:
6

Explanation: Counts are 3, 6, 4, 0; the maximum is 6.

Constraints

- 1 <= T <= 10^5 - 0 <= E[i], L[i] <= 500 - The number of guests on board never becomes negative

Solutions are judged against 2 sample and 10 hidden tests. Sign in to solve it · All problems