Score : $575$ points

问题陈述

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

这些块和切线按顺时针方向编号为 $1, 2, \ldots, N$，并且块 $i$ 的质量为 $A_i$。块 $1$ 也被称为块 $N + 1$。

切线 $i$ 位于块 $i$ 和块 $i + 1$ 之间，它们按顺时针顺序排列：块 $1$，切线 $1$，块 $2$，切线 $2$，$\ldots$，块 $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$ 被切割。

以上为大语言模型 kimi 翻译，仅供参考。

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