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

程式比賽中最重要的莫過於點心了。當然， IOICamp 每天的練習賽也不意外。這天殿壬總共準備了 $N$ 份點心，編號 $1$ 號到 $N$ 號，由左至右、編號由小至大的在長桌上排成了一排，第 $i$ 份點心的好吃程度是 $A_i$ 。不過當然不可能每一份點心都很好吃，因此，有些點心的好吃程度是正的，代表該點心是好吃的，有些點心的好吃程度是負的，代表該點心是難吃的。

為了舒緩大家排隊拿點心時的壅擠程度，殿壬決定將這 $N$ 個點心分為 $K$ 區，每一區都必須包含連續的一些點心。此外，兩個區域之間必須至少相隔 $1$ ，否則就沒有分區的意義了。殿壬當然也不希望有些人會吃到難吃的點心，因此他希望被這 $K$ 區包含的點心的好吃程度總和越大越好！

（具體來說，若殿壬選擇的區域為 $[L_1, R_1], \ldots, [L_K, R_K]$ ，則必須滿足 $L_{i + 1} > R_i + 1, \forall 1 \leq i < K$ 且 $L_i \leq R_i, \forall 1 \leq i \leq K$ ，然後殿壬希望 $\displaystyle\sum_{i = 1}^ {K}{(\sum_{j = L_i}^ {R_i}{A_j})}$ 越大越好。）

不過殿壬很快地又發現，當前的點心順序可能沒辦法安排出很高的好吃程度總和，因此他希望能夠交換一些點心的順序，使得可以規劃出最佳的 $K$ 個區域。由於時間緊迫，殿壬只能對點心們進行至多 $S$ 次操作，每次操作可以選擇 $1 \leq i < j \leq N$ ，然後交換在位置 $i$ 的點心以及在位置 $j$ 的點心。

由於總召殿壬相當忙碌，因此請你幫忙他計算在交換不超過 $S$ 次的情況下，能夠做出的 $K$ 個區域的好吃程度總和最大可以是多少。