Minimum Memory for Hard Drives

Distribute all games among N children; games cannot be split, and every child gets at least one. Any grouping is allowed; groups need not be contiguous in the original array. All disks have the same capacity; find the minimum capacity that fits the distribution. This site uses small sizes that can be solved exactly, and does not substitute contiguous partitioning for arbitrary distribution.

输入格式

The first line contains m N, and the second line contains m game sizes. On this site 1≤N≤m≤15 and 1≤size≤10⁹; these upper bounds are not constraints provided by the source.

输出格式

Output a single integer answer.

样例 1

输入：

5 3
6 7 10 12 1

输出：

13

样例 2

输入：

3 2
8 8 8

输出：

16

样例 3

输入：

3 3
3 9 2

输出：

9

样例说明

Example 1: split into 6+7, 12+1 and 10, with a maximum of 13; with capacity 12, 12 takes a disk alone, 10 can pair with at most 1, and 6 and 7 cannot share a disk, so at least 4 disks are needed; the optimum is 13. Example 2: some child must take two 8s, so the capacity is 16. Example 3: each child gets one game, so the capacity is the maximum, 9.