题目描述

Kevin Sun 想把他珍藏的 $n$ 个牛铃从 Naperthrill 搬到 Exeter，那里的草比玉米更多。在搬家前，他必须把牛铃打包进固定大小的 $k$ 个盒子里。为了保证运输安全，每个盒子里最多只能放两个牛铃。由于 Kevin 想要减少开销，他想知道能用的最小盒子尺寸是多少，以便把所有牛铃装进盒子。

Kevin 是一个细心的牛铃收藏家，他知道第 $i$ ($1 \le i \le n$) 个牛铃的大小是整数 $s_i$ 实际上，他已经将牛铃按照大小排序了，所以对于 $i > 1$，有 $s_{i-1}\le s_i$。同时，作为一个打包高手，Kevin 可以将一个或两个牛铃放入一个盒子中，前提是它们的总大小不超过盒子的大小 $s$。基于这些信息，帮助 Kevin 找到一个最小的盒子尺寸 $s$，使得他能将所有的牛铃装进 $k$ 个盒子里。

输入格式

输入的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \le n \le 2 \cdot k \le 100000$），分别表示牛铃的数量和盒子的数量。

接下来的第二行包含 $n$ 个用空格分隔的整数 $s_1, s_2, ..., s_n$（$1 \le s_1 \le s_2 \le ... \le s_n \le 1000000$），表示 Kevin 的牛铃大小。保证给出的牛铃大小是非递减顺序的。

输出格式

输出一个整数，表示最小的盒子大小 $s$，使得可以将所有牛铃装进 $k$ 个盒子里。

2 1
2 5

7

4 3
2 3 5 9

9

3 2
3 5 7

8

提示

在第一个样例中，Kevin 必须将两个牛铃装进同一个盒子。

在第二个样例中，Kevin 可以将牛铃按以下方式打包：$({2,3})$、(${5}$) 和 (${9}$)。

在第三个样例中，最优的方案是将牛铃打包为 (${3,5}$) 和 (${7}$)。