{"raw_statement":[{"iden":"statement","content":"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.\n\nThus, 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.\n\nThe _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.\n\nYou 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.\n\nFor 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$."},{"iden":"input","content":"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.\n\nThe 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)."},{"iden":"output","content":"In the first line of the output print the maximum possible _total profit_.\n\nIn 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.\n\nIf there are many possible answers, you may print any of them."},{"iden":"examples","content":"Input\n\n8 3\n5 4 2 6 5 1 9 2\n\nOutput\n\n20\n3 2 3\n\nInput\n\n5 1\n1 1 1 1 1\n\nOutput\n\n1\n5\n\nInput\n\n4 2\n1 2000 2000 2\n\nOutput\n\n4000\n2 2"},{"iden":"note","content":"The first example is described in the problem statement.\n\nIn the second example there is only one possible distribution.\n\nIn 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$."}],"translated_statement":[{"iden":"statement","content":"Polycarp 正在练习他的解题能力。他有一个包含 $n$ 道题的列表，难度分别为 $a_1, a_2, dots.h, a_n$。他的计划是恰好练习 $k$ 天。每天他必须从列表中解决至少一道题。Polycarp 按照列表中的顺序解题，不能跳过任何题目。他必须在恰好 $k$ 天内解决所有 $n$ 道题。\n\n因此，每天 Polycarp 解决的是从列表开头开始的一个连续子序列（相邻）问题。他不能跳过题目，也不能重复解题。结果，在 $k$ 天内他将解决所有 $n$ 道题。\n\nPolycarp 练习的第 $j$ 天的 _利润_ 是他在该天解决的所有题目中的最大难度（即，如果他在一天内解决索引从 $l$ 到 $r$ 的题目，则该天的 _利润_ 为 $max limits_(l lt.eq i lt.eq r) a_i$）。他练习的 _总利润_ 是这 $k$ 天利润的总和。\n\n你希望帮助 Polycarp 获得所有合法分配方案中的最大 _总利润_。你的任务是将所有 $n$ 道题分配到 $k$ 天中，满足上述条件，使得 _总利润_ 最大。\n\n例如，若 $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$。\n\n输入的第一行包含两个整数 $n$ 和 $k$ ($1 lt.eq k lt.eq n lt.eq 2000$) —— 题目数量和天数。\n\n第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 2000$) —— Polycarp 列表中题目的难度，按它们在列表中的顺序排列（即 Polycarp 解题的顺序）。\n\n在输出的第一行打印可能的最大 _总利润_。\n\n在第二行打印恰好 $k$ 个正整数 $t_1, t_2, dots.h, t_k$（$t_1 + t_2 + dots.h + t_k$ 必须等于 $n$），其中 $t_j$ 表示 Polycarp 在第 $j$ 天解决的题目数量，以达到最大可能的 _总利润_。\n\n如果有多种可能的答案，你可以输出任意一种。\n\n第一个例子已在题目描述中给出。\n\n在第二个例子中，只有一种可能的分配方式。\n\n在第三个例子中，最佳答案是将题目按以下方式分配：$[ 1, 2000 ], [ 2000, 2 ]$。该分配的 _总利润_ 为 $2000 + 2000 = 4000$。"},{"iden":"input","content":"输入的第一行包含两个整数 $n$ 和 $k$ ($1 lt.eq k lt.eq n lt.eq 2000$) —— 题目数量和天数。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 2000$) —— Polycarp 列表中题目的难度，按它们在列表中的顺序排列（即 Polycarp 解题的顺序）。"},{"iden":"output","content":"在输出的第一行打印可能的最大 _总利润_。在第二行打印恰好 $k$ 个正整数 $t_1, t_2, dots.h, t_k$（$t_1 + t_2 + dots.h + t_k$ 必须等于 $n$），其中 $t_j$ 表示 Polycarp 在第 $j$ 天解决的题目数量，以达到最大可能的 _总利润_。如果有多种可能的答案，你可以输出任意一种。"},{"iden":"examples","content":"输入\n8 3\n5 4 2 6 5 1 9 2\n输出\n20\n3 2 3\n\n输入\n5 1\n1 1 1 1 1\n输出\n1\n5\n\n输入\n4 2\n1 2000 2000 2\n输出\n4000\n2 2"},{"iden":"note","content":"第一个例子已在题目描述中给出。在第二个例子中，只有一种可能的分配方式。在第三个例子中，最佳答案是将题目按以下方式分配：$[ 1, 2000 ], [ 2000, 2 ]$。该分配的 _总利润_ 为 $2000 + 2000 = 4000$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 2000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 1 \\leq a_i \\leq 2000 $.\n\n**Constraints**  \n1. Partition $ A $ into exactly $ k $ contiguous, non-empty subsequences:  \n   $$\n   A = A_1 \\oplus A_2 \\oplus \\cdots \\oplus A_k, \\quad \\text{where each } A_j = (a_{l_j}, a_{l_j+1}, \\dots, a_{r_j})\n   $$\n   with $ 1 = l_1 \\leq r_1 < l_2 \\leq r_2 < \\cdots < l_k \\leq r_k = n $, and $ r_j = l_{j+1} - 1 $ for $ j = 1, \\dots, k-1 $.  \n2. Each $ A_j $ is non-empty: $ r_j - l_j + 1 \\geq 1 $.\n\n**Objective**  \nMaximize the total profit:\n$$\nP = \\sum_{j=1}^{k} \\max_{i \\in [l_j, r_j]} a_i\n$$\nAdditionally, output a partition $ (t_1, t_2, \\dots, t_k) $ where $ t_j = r_j - l_j + 1 $, the length of the $ j $-th segment.","simple_statement":null,"has_page_source":false}