在矮人的地下城市中，有 $N$ 座房屋，按顺时针方向编号为 $1$ 到 $N$。这些房屋由一条环形双向道路连接。已知每相邻两座房屋之间的距离，且每个距离均为正整数。

矮人们喜欢拜访邻居：住在房屋 $i$ 的矮人会拜访住在房屋 $i+1$（当 $i=N$ 时为 $1$）和房屋 $i-1$（当 $i=1$ 时为 $N$）的矮人。然而，他们不喜欢空手而去，因此在离开自己的房屋并到达邻居的房屋之前，他们需要先去一家杂货店购买合适的商品。所访问的杂货店可以位于比邻居房屋更远的地方，也可以位于与邻居房屋相反的方向，矮人可以在路上的任何地点折返。

矮人规划师想要通过拆除所有旧杂货店并新建 $K$ 家杂货店来改造城市，使得矮人拜访邻居时所走的最大距离尽可能小。新杂货店可以建在环形道路上的任意位置，不一定非要建在房屋所在的位置，也不一定非要与现有房屋保持整数距离。请帮助规划师完成这项任务，并编写一个算法，计算在 $K$ 家杂货店位置最优的情况下，矮人拜访邻居并顺路去杂货店所走的最大距离。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示房屋的数量和要建造的杂货店数量。

第二行包含 $N$ 个正整数 $d_1, \dots, d_N$，表示沿顺时针方向房屋 $i$ 与 $i+1$（当 $i=N$ 时为 $1$）之间的道路距离。

数据范围

$2 \le N \le 500\,000$，$1 \le K \le N$，$1 \le d_i \le 10^9$。

输出格式

输出一个整数，表示在 $K$ 家杂货店位置最优的情况下，矮人拜访邻居并顺路去杂货店所走的最大距离的最小值。可以证明结果总是一个整数。

样例

样例输入 1

3 1
2 4 5

样例输出 1

6

样例输入 2

5 3
2 6 4 1 5

样例输出 2

6