TopCoder

PCC

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

78.9% (15/19)

Tags

Description

大荒之地,北境綿延的靈脈河谷自西向東可分為 $N$ 處穴位,第 $i$ 處穴位的「靈氣充沛程度」以正整數 $a_i$ 表示,數值越高,仙人駐守時能施展的法力越強。

為守護整片河谷的靈脈,門派需在整條河谷上布置大結界,形成完整防護。門派因弟子有限,僅能派遣恰好 $K$ 對弟子駐守穴位,形成 $K$ 組「陣基」。第 $j$ 組陣基座落於連續穴位 $[L_j, R_j]$ 上,每組陣基由兩位弟子組成,稱為「左右護法」,他們鎮守陣基範圍的兩端,特別的,左右護法可以駐守同一穴位,以增強結界的防禦力。陣基範圍不得重疊且必須緊密相連,以保證大結界的完整與穩定。

每組陣基的防禦力由左右護法所在穴位的靈氣總和決定,也就是第 $j$ 組陣基的防禦力為 $a_{L_j} + a_{R_j}$。整條河谷的大結界防禦力,則是所有陣基防禦力的總和。

大結界的威力依附於各陣基兩端的護法,只要護法穩守陣基,結界就能完整護衛其所覆蓋的穴位。請你協助門派長老,巧妙安排護法的駐守位置,使整片靈脈河谷的大結界防禦力發揮到最大。

Input Format

第一行輸入兩個正整數 $N, K$,以空格隔開,分別表示「穴位數量」與「陣基數量」。

第二行輸入 $N$ 個正整數 $a_1, a_2, \dots, a_N$,以空格隔開,分別表示穴位的「靈氣充沛程度」。

  • $1 \leq K \leq N \leq 2 \times 10^ 5$
  • $1 \leq a_i \leq 10^ 9$

Output Format

共一行,輸出一個正整數,代表最大可能的「大結界防禦力」。

Sample Input 1

5 3
4 5 10 8 2

Sample Output 1

39

Sample Input 2

7 6
3 6 1 7 1 4 8

Sample Output 2

55

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~8 $N \leq 500$。 10
3 0~13 $N \leq 5000$。 20
4 0~22 無特別限制。 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3 4
1 1000 524288 65536 1 2 3 4
2 1000 524288 65536 2 3 4
3 1000 524288 65536 2 3 4
4 1000 524288 65536 2 3 4
5 1000 524288 65536 2 3 4
6 1000 524288 65536 2 3 4
7 1000 524288 65536 2 3 4
8 1000 524288 65536 2 3 4
9 1000 524288 65536 3 4
10 1000 524288 65536 3 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 4
15 1000 524288 65536 4
16 1000 524288 65536 4
17 1000 524288 65536 4
18 1000 524288 65536 4
19 1000 524288 65536 4
20 1000 524288 65536 4
21 1000 524288 65536 4
22 1000 524288 65536 4