TopCoder

User's AC Ratio

75.0% (6/8)

Submission's AC Ratio

22.7% (15/66)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬六歲又兩天大時的故事。

這天殿壬找來他的 $K - 1$ 個朋友(因此共 $K$ 人)一起來玩卡牌遊戲,由於殿壬是天才兒童,他的卡牌當然非比尋常:共有 $N$ 張卡牌,第 $i$ 張卡牌上面寫了 $a_i$ 這個數字。這 $N$ 張牌照著 $1$ 到 $N$ 的順序在桌子上從左至右排開。
他們玩的是合作遊戲,由第一個人(殿壬) 開始,每個人從目前卡牌的最左邊開始,拿走若干張連續的卡牌並自己收起來。每個人都至少要拿走一張卡牌,且最後一個人必須拿走剩下全部的卡牌。

等到 $K$ 個人都拿完了以後,每個人會計算自己的得分,一個人的得分為他拿走的卡牌中,寫著的最大數字與最小數字的差。每個人計算完了以後,再將 $K$ 個人的得分加總就是團體得分了。

由於殿壬是天才兒童,因此他希望他與朋友獲得的得分能越小越好。請你幫忙算算看,所有拿法當中,最小可能的得分為多少?

Input Format

輸入第一行有兩個正整數 $N, K$ ,代表卡牌的數量以及玩遊戲的人(殿壬與他的朋友們)。
接著一行有 $N$ 個正整數 $a_1, a_2, \ldots, a_N$ ,代表卡牌上寫的數字。

  • $1 \leq N \leq 2 \times 10^ 4$
  • $1 \leq K \leq \min(N, 20)$
  • $1 \leq a_i \leq 10^ 9 $

Output Format

輸出一個整數代表所有可能的拿法中,最小的得分。

Sample Input

4 2
4 1 2 3

Sample Output

2

Hints

第一個人先拿走 $4$ ,獲得得分 $0$ ,第二個人再拿走 $1, 2, 3$ ,獲得得分 $2$ 。

Problem Source

Subtasks

No. Testdata Range Score
1 0~40 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144 1
1 2000 262144 262144 1
2 2000 262144 262144 1
3 2000 262144 262144 1
4 2000 262144 262144 1
5 2000 262144 262144 1
6 2000 262144 262144 1
7 2000 262144 262144 1
8 2000 262144 262144 1
9 2000 262144 262144 1
10 2000 262144 262144 1
11 2000 262144 262144 1
12 2000 262144 262144 1
13 2000 262144 262144 1
14 2000 262144 262144 1
15 2000 262144 262144 1
16 2000 262144 262144 1
17 2000 262144 262144 1
18 2000 262144 262144 1
19 2000 262144 262144 1
20 2000 262144 262144 1
21 2000 262144 262144 1
22 2000 262144 262144 1
23 2000 262144 262144 1
24 2000 262144 262144 1
25 2000 262144 262144 1
26 2000 262144 262144 1
27 2000 262144 262144 1
28 2000 262144 262144 1
29 2000 262144 262144 1
30 2000 262144 262144 1
31 2000 262144 262144 1
32 2000 262144 262144 1
33 2000 262144 262144 1
34 2000 262144 262144 1
35 2000 262144 262144 1
36 2000 262144 262144 1
37 2000 262144 262144 1
38 2000 262144 262144 1
39 2000 262144 262144 1
40 2000 262144 262144 1