#P18304. Groceries

Groceries

Groceries

矮人的地下城里有 NN 栋房屋,按顺时针方向编号为 11 到 NN。所有房屋由一条可以双向通行的环形道路连接,每两栋相邻房屋之间沿道路的距离都是已知的正整数。

矮人喜欢拜访邻居。住在第 ii 栋房屋的矮人会拜访第 i+1i+1 栋和第 i−1i-1 栋房屋中的矮人,其中第 NN 栋的下一个邻居是第 11 栋,第 11 栋的上一个邻居是第 NN 栋。但是,矮人不喜欢空手拜访:从自己家出发后、到达邻居家之前,必须先到一家杂货店购买礼物。杂货店可以比邻居家更远,也可以位于相反方向;矮人在途中可以在任意位置折返。

规划师决定拆除所有旧杂货店,并重新建造 KK 家杂货店,使矮人拜访邻居时所需行走距离的最大值尽可能小。新杂货店可以建在环形道路上的任意位置,不必与房屋重合,也不必与已有房屋相距整数距离。

对给定的杂货店布局,每次拜访都可以自行选择杂货店与行走路线,以使该次拜访的路程最短。请计算最优布局下,所有这些拜访的最短路程的最大值。

输入格式

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

第二行包含 NN 个正整数 d1,…,dNd_1,\ldots,d_N。当 1≤i<N1\le i<N 时,did_i 是从第 ii 栋房屋顺时针走到第 i+1i+1 栋房屋的道路长度;dNd_N 是从第 NN 栋房屋顺时针走到第 11 栋房屋的道路长度。

输入仅有一组数据。

输出格式

输出一个整数,表示最优布局下,矮人拜访邻居并在途中经过一家杂货店所需行走距离的最小可能最大值。

可以证明答案总是整数。

数据范围

  • 2≤N≤500 0002\le N\le500\,000;
  • 1≤K≤N1\le K\le N;
  • 1≤di≤1091\le d_i\le10^9。

样例 1

3 1
2 4 5
6

一种最优方案是将杂货店建在长度为 44 的道路段的中点。

样例 2

5 3
2 6 4 1 5
6