股票獲利

題目敘述

$Joe$在一間股票投資公司工作，他的上司為了測試他對於股票買賣的能力給了他一個小練習：

考慮連續$N$天的股票價格，以$P[1],P[2],...P[n]$表示，以及一個整數$K$，找出$M$對天數

$(b_1,s_1),(b_2,s_2),...(b_m,s_m)$

使得使得$M\leq K$，且，且$1\leq b_1 < s_1 < b_2 < s_2 < ... < b_m < s_m \leq n$，對於每一個對於每一個$(b_t,s_t)$，$Joe$會在第$b_t$天買1000張股票，然後在第$s_t$天全部賣出，因此總獲利可以表示為$1000 \sum_{t=1}^{m}(p[s_t]-p[b_t])$。

給你$K,K\leq N/2$，你能找到$M,M\leq K$對天數，使得獲利最大化嗎?

輸入說明

一開始有一個整數$T$，表示有$T$筆測資。每筆測資第一行有兩個整數$N,K$，表示有$N$天，最多要找$K$對。接下來下一行有$N$個數字，依序表示這$N$天的股票價格。

保證

$1\leq T\leq 20$
$1\leq N\leq 1000$
$0\leq P[i]\leq 1000$
輸出說明

輸出一行，為最大可行的獲利最多是多少。

範例輸入

範例輸出

2000
0
6000

配分方法

配分	限制
25%	$N\leq 10$
25%	$N\leq 50$
25%	$N\leq 100$
25%	$N\leq 1000$
時限	100ms
記憶體	5120000 kb

Judge Setting

run-time limit: 100 ms
memory limit: 5120000 byte
測資數量: 0

40. 股票獲利