大荒之地,北境綿延的靈脈河谷自西向東可分為 $N$ 處穴位,第 $i$ 處穴位的「靈氣充沛程度」以正整數 $a_i$ 表示,數值越高,仙人駐守時能施展的法力越強。
為守護整片河谷的靈脈,門派需在整條河谷上布置大結界,形成完整防護。門派因弟子有限,僅能派遣恰好 $K$ 對弟子駐守穴位,形成 $K$ 組「陣基」。第 $j$ 組陣基座落於連續穴位 $[L_j, R_j]$ 上,每組陣基由兩位弟子組成,稱為「左右護法」,他們鎮守陣基範圍的兩端,左右護法不得駐守同一穴位,以維持結界的張力。陣基範圍不得重疊且必須緊密相連,以保證大結界的完整與穩定。
每組陣基的防禦力由左右護法所在穴位的靈氣總和決定,也就是第 $j$ 組陣基的防禦力為 $a_{L_j} + a_{R_j}$。整條河谷的大結界防禦力,則是所有陣基防禦力的總和。
大結界的威力依附於各陣基兩端的護法,只要護法穩守陣基,結界就能完整護衛其所覆蓋的穴位。請你協助門派長老,巧妙安排護法的駐守位置,使整片靈脈河谷的大結界防禦力發揮到最大。
第一行輸入兩個正整數 $N, K$,以空格隔開,分別表示「穴位數量」與「陣基數量」。
第二行輸入 $N$ 個正整數 $a_1, a_2, \dots, a_N$,以空格隔開,分別表示穴位的「靈氣充沛程度」。
共一行,輸出一個正整數,代表最大可能的「大結界防禦力」。
5 2 4 5 10 8 2
24
7 1 3 6 1 7 1 4 8
11
10 3 1 1 1 1 1 1 1 1 1 1
6
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資。 | 0 |
| 2 | 0~10 | $N \leq 500$。 | 10 |
| 3 | 0~15 | $N \leq 5000$。 | 20 |
| 4 | 0~26 | 無特別限制。 | 70 |