Load Balancing

Assign m tasks in the given order to n resources so that each resource receives a non-empty contiguous range of tasks. Minimize the maximum total load over all resources.

See below for this site's input/output protocol.

输入格式

The first line contains n m, and the next line contains m processing times. 1≤n≤m≤100000, 1≤burstTime[i]≤10000.

输出格式

Output the minimum possible maximum resource load.

样例 1

输入：

3 5
7 2 3 4 5

输出：

9

样例 2

输入：

2 3
1 1 1

输出：

2

样例 3

输入：

1 3
1 2 3

输出：

6