Kevin Sun 想要把他珍贵的 n 个牛铃收藏从 Naperthrill 搬到埃克塞特,那里实际上是草而不是玉米。在移动之前,他必须将牛铃装入 k 个固定尺寸的盒子中。为了保证他的藏品在运输过程中的安全,他不会在一个盒子里放入两个以上的牛铃。由于凯文希望最大限度地减少开支,因此他对可以用来包装整个收藏品的最小尺寸的盒子感到好奇。
Kevin 是一位细心的牛铃收藏家,他知道他的第 i 个 (1 ≤ i ≤ n) 牛铃的大小是整数 si。事实上,他将牛铃按大小排序,因此对于任何 i > 1,si - 1 ≤ si。Kevin 也是一位包装专家,当且仅当它们的大小总和不超过 s 时,Kevin 才能将一到两个牛铃放入大小为 s 的盒子中。根据这些信息,帮助 Kevin 确定可以将所有牛铃放入 k 个大小为 s 的盒子中的最小 s。
输入
输入的第一行包含两个空格分隔的整数 n 和 k (1 ≤ n ≤ 2·k ≤ 100 000),分别表示牛铃的数量和盒子的数量。
下一行包含 n 个空格分隔的整数 s1, s2, ..., sn (1 ≤ s1 ≤ s2 ≤ ... ≤ sn ≤ 1 000 000),即 Kevin 牛铃的大小。保证尺寸 si 按非递减顺序给出。
输出
打印一个整数,即凯文可以将其所有牛铃放入 k 个大小为 s 的盒子中的最小 s。
示例
输入 #1
2 1 2 5
输出 #1
7
输入 #2
4 3 2 3 5 9
输出 #2
9
输入 #3
3 2 3 5 7
输出 #3
8
注意
在第一个示例中,Kevin 必须将他的两个牛铃装入同一个盒子中。
在第二个示例中,Kevin 可以将以下几组牛铃组合在一起:{2, 3}、{5} 和 {9}。
在第三个示例中,最优解是 {3, 5} 和 {7}。