13681368 SUSTech Online Judge
Problem 1368 --[Bonus] Division

1368: [Bonus] Division

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 598  Solved: 215
[Submit][Status][Web Board]

Description

Given an array with n integers (a1, a2, ..., an). You need to divide it into m consecutive subarrays,
which indicates that each element should be assigned to exact one subarray. Try to maximize the following formulations:
S(i) indicates the index of subarray that ai belongs to. (Subarrays are counted starting from 1 to m and from left to right.)


What is the maximum value you can achieve?

Input

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 3*105).

The second line contains n integers a1, a2, ..., an (|ai| ≤ 106).

Output

For each test case, output the maximum value you can obtain.

Sample Input

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

Sample Output

-45

HINT

Source

 

[Submit][Status]