103705: [Atcoder]ABC370 F - Cake Division

Problem Statement

There is a circular cake divided into $N$ pieces by cut lines. Each cut line is a line segment connecting the center of the circle to a point on the arc.

The pieces and cut lines are numbered $1, 2, \ldots, N$ in clockwise order, and piece $i$ has a mass of $A_i$. Piece $1$ is also called piece $N + 1$.

Cut line $i$ is between pieces $i$ and $i + 1$, and they are arranged clockwise in this order: piece $1$, cut line $1$, piece $2$, cut line $2$, $\ldots$, piece $N$, cut line $N$.

We want to divide this cake among $K$ people under the following conditions. Let $w_i$ be the sum of the masses of the pieces received by the $i$-th person.

• Each person receives one or more consecutive pieces.
• There are no pieces that no one receives.
• Under the above two conditions, $\min(w_1, w_2, \ldots, w_K)$ is maximized.

Find the value of $\min(w_1, w_2, \ldots, w_K)$ in a division that satisfies the conditions, and the number of cut lines that are never cut in the divisions that satisfy the conditions. Here, cut line $i$ is considered cut if pieces $i$ and $i + 1$ are given to different people.

Constraints

• $2 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^4$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Let $x$ be the value of $\min(w_1, w_2, \ldots, w_K)$ in a division that satisfies the conditions, and $y$ be the number of cut lines that are never cut. Print $x$ and $y$ in this order, separated by a space.

Sample Input 1

5 2
3 6 8 6 4

Sample Output 1

13 1

The following divisions satisfy the conditions:

• Give pieces $2, 3$ to one person and pieces $4, 5, 1$ to the other. Pieces $2, 3$ have a total mass of $14$, and pieces $4, 5, 1$ have a total mass of $13$.
• Give pieces $3, 4$ to one person and pieces $5, 1, 2$ to the other. Pieces $3, 4$ have a total mass of $14$, and pieces $5, 1, 2$ have a total mass of $13$.

The value of $\min(w_1, w_2)$ in divisions satisfying the conditions is $13$, and there is one cut line that is not cut in either division: cut line $5$.

Sample Input 2

6 3
4 7 11 3 9 2

Sample Output 2

11 1

Sample Input 3

10 3
2 9 8 1 7 9 1 3 5 8

Sample Output 3

17 4

问题陈述

有一个圆形蛋糕，被N条切线分成了N块。每条切线都是连接圆心到圆弧上一点的线段。

块和切线按顺时针方向编号为1, 2, …, N，第i块的质量为A_i。第1块也可以称为第N + 1块。

第i条切线位于第i块和第i + 1块之间，它们按顺时针顺序排列：第1块，第1条切线，第2块，第2条切线，…，第N块，第N条切线。

我们想要在以下条件下将这块蛋糕分给K个人。设w_i是第i个人收到的蛋糕块的总质量。

• 每个人收到一个或多个连续的块。
• 没有蛋糕块是无人接收的。
• 在上述两个条件下，最大化$\min(w_1, w_2, \ldots, w_K)$。

找出满足条件的分配中$\min(w_1, w_2, \ldots, w_K)$的值，以及满足条件的分配中从未被切割的切线数量。这里，如果第i块和第i + 1块被分给不同的人，则第i条切线被认为是被切割的。

约束条件

• $2 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^4$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

输出

设$x$为满足条件的分配中$\min(w_1, w_2, \ldots, w_K)$的值，$y$为满足条件的分配中从未被切割的切线数量。按顺序打印$x$和$y$，中间用一个空格分隔。

样本输入1

5 2
3 6 8 6 4

样本输出1

13 1

以下分配满足条件：

• 将第2块和第3块给一个人，将第4块、第5块和第1块给另一个人。第2块和第3块的总质量为14，第4块、第5块和第1块的总质量为13。
• 将第3块和第4块给一个人，将第5块、第1块和第2块给另一个人。第3块和第4块的总质量为14，第5块、第1块和第2块的总质量为13。

满足条件的分配中$\min(w_1, w_2)$的值为13，且有一条切线在两种分配中都没有被切割：第5条切线。

样本输入2

6 3
4 7 11 3 9 2

样本输出2

11 1

样本输入3

10 3
2 9 8 1 7 9 1 3 5 8

样本输出3

17 4