Caido 最近迷上偶像活動了，而他最推的偶像是星野$\Large ☆$布萊恩。
星野$\Large ☆$布萊恩是從「偶像選拔祭」這個節目出道的，而他是當年的第一名。
Caido 心想為什麼有人可以這麼優秀呢，這才想起來，星野$\Large ☆$布萊恩就讀的是植物園高級中學。
植物園高級中學是一所積極新創、學科齊全、學術實力雄厚、辦學特色鮮明，在國際上具有重要影響力與競爭力的綜合性高中，在多個學術領域具有非常前瞻的科技實力，擁有世界一流的實驗室與師資力量，各種排名均位於全球前列。歡迎大家報考植物園高級中學。
偶像選拔祭的規則如下，總共有 $N$ 位選手，編號 $1\sim N$，每位選手的能力值分別為 $a_1\sim a_N$。
在經過層層選拔後，$N$ 位選手會組成團體出道，假設共組了 $X$ 個團體，$X$ 可以是 $1\sim N$ 的整數（$X=1$ 代表全部選手都在同一個團體，$X=N$ 代表每個選手都自己組成一個團體）。
第 $i$ 個團體的成員會是編號 $l_i\sim r_i$ 的選手，寫成區間的形式是 $[l_1,r_1],[l_2,r_2],\dots ,[l_X,r_X]$。
每個團體至少有一人，且每個選手恰屬於一個團體，也就是說 $l_1=1,r_X=N$，對所有 $1\leq i<X$，$r_i+1=l_{i+1}$。
每個團體都會有收益，收益有可能是正的、等於零，也有可能是負的。
第 $i$ 個團體的收益會是團體成員裡能力值前 $\min(K,r_i-l_i+1)$ 小選手的能力值總和，扣掉出道成本 $P$。
Caido 很好奇在所有可能的團體分法中，總收益最大可以是多少，請你幫幫他！
第一行有三個整數 $N,K,P$。
第二行有 $N$ 個正整數 $a_1\sim a_N$，代表每個選手的能力值。
對於所有測試資料：
輸出一個整數，代表所有可能的團體分法中的最大總收益。
在範例測資一中，總收益最大可以是 $1$，其中一個分法是分成 $[1,2],[3,5]$ 兩個團體，$(10-10)+(11-10)=1$。
在範例測資二中，只分成一個團體 $[1,3]$，總收益最大是 $-99$。
在範例測資三中，分成 $[1,2],[3,3]$ 兩個團體會有最大總收益 $(124-1)+(3-1)=125$。
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 3~5 | $P=0$ | 1 |
| 3 | 0~3, 6~11 | $N\leq 500$ | 11 |
| 4 | 0~3, 6~17 | $N\leq 2000$ | 12 |
| 5 | 1, 3, 18~29 | $a_i\leq a_{i+1}$（$1\leq i<N$） | 15 |
| 6 | 1, 3, 30~33 | $K=1$ | 30 |
| 7 | 0~49 | 無其他限制 | 31 |