Given an array A of n integers. You can perform the following operation at most k times:
- Pick 2 indices l,r such that 1≤l≤r≤n, assign 0 to each element Al,Al+1,...,Ar.
Find the maximum possible sum of elements in A after performing some operations?
### Input
- The first line contains 2 integers n,k.
- The second line contains n integers Ai.
### Output
- Print the maximum possible sum of A.
### Constraints
- 1≤n,k≤5000.
- |Ai|≤109.
### Example
Input:
411-31-10
Output:
1
