Weasel finds Staircase

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Weasel loves histograms. Weasel feels that he is very much out of shape and asks for Chef’s advice. Chef convinced Weasel that the only way to get back in shape is to work out. Weasel decides to follow Chef’s advice and has formulated the greatest workout plan  to reflect his love for histograms  in which he will go down the staircase every day. However, Weasel is not in the best shape, so, for starters, he can only go down at most K steps.
Formally, a staircase is a set of adjacent rectangles with at most K changes of height. These rectangles should have either increasing or decreasing heights. The rectangles should start from the bottom (see images in the explanation section for clarification), and the height of rectangle at ith position shouldn't be more than histogram_{i}.
For each of the T cases, you have to find the greatest area of a staircase that matches the abovementioned restrictions.
Input
The first line of the input contains an integer T, denoting the number of test cases.
For each of the T cases, you will be given two integers N, denoting the number of elements of the histogram, and K, the maximum number of steps, on the first line.
For each of the T cases, you will be given histogram array on the second line.
Output
For each test case you should print an integer, the maximum area of a staircase that satisfies Weasel's conditions.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 10^{5}
 0 ≤ K ≤ 50
 The sum of N over all testcases does not exceed 10^{5}.
 0 ≤ histogram_{i} ≤ 10^{5}
Subtasks
 Subtask #1 (10 points): K = 0.
 Subtask #2 (30 points): The sum of N over all testcases does not exceed 1,500.
 Subtask #3 (60 points): original constraints
Example
Input: 4 5 2 1 2 3 4 5 5 3 9 8 7 6 4 5 1 8 7 5 7 8 4 10 0 1 1 0 Output: 13 33 29 2
Explanation
The cells which form the staircase are colored with yellow. The discarded cells are colored with grey.
Case 1:
The computed area is 1 + 2 × 2 + 4 × 2 = 13.
There are 2 changes of height: we start with a height of 1, we change to 2 and then we change to 4.
Case 2:
The computed area is 9 + 7 × 2 + 6 + 4 = 33.
Case 3:
The computed area is 7 × 2 + 5 × 3 = 29.
Here is another possible solution:
Case 4:
We take the second and the third cell. We have 0 changes in height. This is a viable solution because we can also have staircases with less than K changes.
Author:  bciobanu 
Tester:  jingbo_adm 
Editorial  https://discuss.codechef.com/problems/WEASELSC 
Tags  bciobanu, dynamicprogramming, medhard, persistentconvex, sept17 
Date Added:  13082017 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 