蛋糕分配

题目描述

有一个圆形蛋糕,被分割线分成 $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$ 被切割。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

设满足条件的分法中 $\min(w_1, w_2, \ldots, w_K)$ 的值为 $x$,从未被切割的分割线的条数为 $y$。按此顺序输出 $x$ 和 $y$,以空格分隔。

样例

5 2
3 6 8 6 4

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$,且任一分法中都不被切割的分割线有 1 条:分割线 $5$。

6 3
4 7 11 3 9 2

11 1

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

17 4

数据范围

• $2 \le K \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^4$
• 所有输入值均为整数。