← 返回题目列表

Codeforces · 604/B

B. 更多牛铃

中文机器翻译题面 查看原题

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}。