题目描述

假设有n个任务由k个可并行工作的机器完成。

完成i号任务需要的时间为ti,一旦号任务分配给某台机器,则中途不能更换机器。

试设计一个算法找出完成这n个任务的最佳调度,使得完成全部任务的时间最早。

输入

第一行有两个正整数n和k。

第二行的n个正整数是完成n个任务需要的时间。

输出

完成全部任务的最早时间。

样例

样例 1

输入

7 3
2 14 4 16 6 5 3

输出

17
样例 2

输入

5 2
8 9 3 7 7

输出

17

提示

1 \leq n \leq 18 ,1 \leq k \leq 8