CF1006B.Polycarp's Practice

Polycarp is practicing his problem solving skill. He has a list of $n$ problems with difficulties $a_1, a_2, \dots, a_n$, respectively. His plan is to practice for exactly $k$ days. Each day he has to solve at least one problem from his list. Polycarp solves the problems in the order they are given in his list, he cannot skip any problem from his list. He has to solve all $n$ problems in exactly $k$ days.

Thus, each day Polycarp solves a contiguous sequence of (consecutive) problems from the start of the list. He can't skip problems or solve them multiple times. As a result, in $k$ days he will solve all the $n$ problems.

The profit of the $j$-th day of Polycarp's practice is the maximum among all the difficulties of problems Polycarp solves during the $j$-th day (i.e. if he solves problems with indices from $l$ to $r$ during a day, then the profit of the day is $\max\limits_{l \le i \le r}a_i$). The total profit of his practice is the sum of the profits over all $k$ days of his practice.

You want to help Polycarp to get the maximum possible total profit over all valid ways to solve problems. Your task is to distribute all $n$ problems between $k$ days satisfying the conditions above in such a way, that the total profit is maximum.

For example, if $n = 8, k = 3$ and $a = [5, 4, 2, 6, 5, 1, 9, 2]$, one of the possible distributions with maximum total profit is: $[5, 4, 2], [6, 5], [1, 9, 2]$. Here the total profit equals $5 + 6 + 9 = 20$.

Polycarp 正在练习他的解题能力。他有一份包含 $n$ 道题的列表，各题难度分别为 $a_1, a_2, \dots, a_n$。他计划恰好练习 $k$ 天，且每天必须至少解决列表中的一道题。Polycarp 必须按列表中给出的顺序解题，不能跳过任何题目，且必须在恰好 $k$ 天内解决全部 $n$ 道题。

因此，每天 Polycarp 解决的是列表开头一段连续的题目序列。他既不能跳过题目，也不能重复解题。最终，他在 $k$ 天内将解决全部 $n$ 道题。

第 $j$ 天的收益定义为 Polycarp 在该天所解所有题目的难度中的最大值（即：若某天他解的是下标从 $l$ 到 $r$ 的题目，则当天的收益为 $\max\limits_{l \le i \le r}a_i$）。整个练习的总收益为 $k$ 天收益之和。

你希望帮助 Polycarp 实现所有合法解题方案中可能达到的最大总收益。你的任务是将全部 $n$ 道题分配到 $k$ 天中，满足上述条件，并使得总收益最大化。

例如，当 $n = 8,\ k = 3$ 且 $a = [5, 4, 2, 6, 5, 1, 9, 2]$ 时，一种能达到最大总收益的分配方案为：$[5, 4, 2],\ [6, 5],\ [1, 9, 2]$。此时总收益为 $5 + 6 + 9 = 20$。

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$) — the number of problems and the number of days, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2000$) — difficulties of problems in Polycarp's list, in the order they are placed in the list (i.e. in the order Polycarp will solve them).

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2000$），分别表示问题的数量和天数。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2000$），表示 Polycarp 列表中各问题的难度，按其在列表中的顺序给出（即 Polycarp 将按此顺序求解这些问题）。

In the first line of the output print the maximum possible total profit.

In the second line print exactly $k$ positive integers $t_1, t_2, \dots, t_k$ ($t_1 + t_2 + \dots + t_k$ must equal $n$), where $t_j$ means the number of problems Polycarp will solve during the $j$-th day in order to achieve the maximum possible total profit of his practice.

If there are many possible answers, you may print any of them.

在输出的第一行打印最大可能的总收益。

在第二行打印恰好 $k$ 个正整数 $t_1, t_2, \dots, t_k$（需满足 $t_1 + t_2 + \dots + t_k = n$），其中 $t_j$ 表示 Polycarp 在第 $j$ 天解决的问题数量，以实现其训练的最大可能总收益。

若存在多种可能的答案，可任选其一输出。

The first example is described in the problem statement.

In the second example there is only one possible distribution.

In the third example the best answer is to distribute problems in the following way: $[1, 2000], [2000, 2]$. The total profit of this distribution is $2000 + 2000 = 4000$.

第一个示例已在题目描述中给出。

第二个示例中仅存在一种可能的分配方式。

第三个示例中，最优解是按如下方式分配题目：$[1, 2000], [2000, 2]$。该分配方式的总收益为 $2000 + 2000 = 4000$。