DER UNTERGANG - 坦克射手

題目敘述

兩年半後，柏林 1945年3月20日，元首的56歲生日，地堡中的洪普斯被巨大的聲響吵醒「是大砲」「別傻了，怎麼會有大炮呢」「你說的對，這不是空投炸彈，這就是大砲，俄國人已經來了，多好的生日禮物啊」，另一邊元首正在憤怒的和柯勒通著電話「俄國人應該已經佔領了奧多河上的一座鐵路橋，離市中心只有12公里，俄國人已經到這麼近啦，應該把德國空軍高層通通都絞死！」碰的一聲他掛斷了電話。

由於情勢急迫，元首決定實施``克勞塞維茲戰略''，也就是將大部分人員撤離柏林，但是元首他堅持留在柏林，他的幕僚們都認為柏林守不住了，紛紛勸元首離開，其中希姆萊甚至打算與艾森豪威爾進行談話「見了艾森豪威爾我是該和行納粹禮還是握手呢」雖然這是叛國罪但這種情況還真是沒其他辦法啊。

經過一番對話，官員們都認為元首已經失去理智了，他要調動的軍隊根本不存在，他在紙上談兵。的確，斯坦納的軍隊已經軍心渙散，自身難保，怎麼可能來支援元首呢？現在要斯坦那發動進攻，太荒唐了。元首這時穿著他的大衣來到地面，者裡聚集了柏林希特勒青年軍最成功的坦克射手

希特勒青年軍們按順序排成一排，準備迎接元首的到來，他們每個人身上都有一個數字，長官為了製造更好的視覺效果，想要由左到右從這些孩子中找出$k$個區段，第$i$個區段必須包含$i$個小孩，想要使的每一區段的小孩身上數字和的平方的總和最大，才能給元首最震撼的效果。換言之假設有$N$個孩子，第$i$個孩子身上的數字為$a_i$，則我們要選出$1 \leq L_1 \leq R_1 < L_2 \leq R_2<...< L_k \leq R_k \leq N$使得 $$\sum^{K}_{i=1}(\sum^{R_i}_{j=L_i}a_j)^2 \; 最大$$ 「我的元首，這小子用反坦克炮彈摧毀了兩輛俄國坦克，他叫"彼得.克蘭茲"」「那麼你就是彼得了，希望我的將軍能有你這般勇氣」，元首捏了一下彼得的臉頰，這也是元首最後一次來到地面。

InputFile

第一行有兩個數字$N(1 \leq N \leq 10^5),k(1 \leq k \leq 100)$接著第二行有$N$個數字$a_1 \sim a_N(-10^6 \leq a_i \leq 10^6)$依序為青年軍身上的數字

保證$k(k+1)/2 \leq N$。

OutputFile

請輸出長官能得到的最大答案，元首看了會很開心的

範例輸入

5 2
3 4 3 7 1

範例輸出

Explanations

在第一筆測資中，我們選擇(4)、(3 7)這兩段區間，滿足題目條件且可以得到最大的答案$4^2+(3+7)^2=116$

限制:

時限	1000ms
記憶體	65536000 bytes

Judge Setting

run-time limit: 1000 ms
memory limit: 65536000 byte
測資數量: 0