Array Splitting

题意翻译

给定序列 $a_1, a_2, \cdots, a_n$ 和整数 $k$，你的任务是将 $a_1, a_2, \cdots, a_n$ 分成 $k$ 段，每个段从左到右的编号依次是 $1,2,\cdots, k$ 令 $f(i)$ 表示位置 $i$ 属于的段的编号，你需要让 $ \sum\limits_{i=1}^{n} (a_i \cdot f(i)) $ 最大。输出这个最大值。

题目描述

You are given an array $ a_1, a_2, \dots, a_n $ and an integer $ k $ . You are asked to divide this array into $ k $ non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray. Let $ f(i) $ be the index of subarray the $ i $ -th element belongs to. Subarrays are numbered from left to right and from $ 1 $ to $ k $ . Let the cost of division be equal to $ \sum\limits_{i=1}^{n} (a_i \cdot f(i)) $ . For example, if $ a = [1, -2, -3, 4, -5, 6, -7] $ and we divide it into $ 3 $ subbarays in the following way: $ [1, -2, -3], [4, -5], [6, -7] $ , then the cost of division is equal to $ 1 \cdot 1 - 2 \cdot 1 - 3 \cdot 1 + 4 \cdot 2 - 5 \cdot 2 + 6 \cdot 3 - 7 \cdot 3 = -9 $ . Calculate the maximum cost you can obtain by dividing the array $ a $ into $ k $ non-empty consecutive subarrays.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 3 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ |a_i| \le 10^6 $ ).

输出格式

Print the maximum cost you can obtain by dividing the array $ a $ into $ k $ nonempty consecutive subarrays.

输入输出样例

输入样例 #1

5 2
-1 -2 5 -4 8

输出样例 #1

15

输入样例 #2

7 6
-3 0 -1 -2 -2 -4 -1

输出样例 #2

-45

输入样例 #3

4 1
3 -1 6 0

输出样例 #3

8