Get Minimum Value

Pass the levels in order; level i deducts power[i] health, and health must stay strictly greater than 0 at all times. Armor may be used on at most one level to cancel min(armor,power[i]) damage. Find the minimum initial health.

输入格式

The first line contains n armor; the second line contains the damage values. 1≤n≤100000, 1≤damage,armor≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

4 5
1 2 6 7

输出：

12

样例 2

输入：

3 1
1 2 3

输出：

6

样例 3

输入：

1 10
5

输出：

1

样例说明

The answers are 12, 6 and 1. Even if all damage is blocked, at least 1 health is still required.