輸入一個大小為 \(N\) 的一維整數陣列 \(p[i]\)，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個:子陣列範圍小於 \(3\) 或切到給定的層級 \(K\) 就不再切割。 而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，也就是說，若區段的範圍是\([s,t]\)，則要找出切點 \(m \in [s+1,t-1]\)，使得 \(|\sum_{i=s}^t{p[i] \times (i- m)}|\) 越小越好，如果有兩個最佳切點，則選擇編號較小的。

輸入格式

第一行有兩個正整數 \(N\) 與 \(K\)。 第二行有 \(N\) 個正整數，代表陣列內容 \(p[1]\) \( \)p[N]\(， 數字間以空白隔開，總和不超過\)10^9,N \leq50000\(，切割層級限制 \)K<30~。

輸出格式

所有切點的 \(p[i]\)值總和。

範例輸入1

7 3
2 4 1 3 7 6 9

範例輸入2

5 1
1 2 3 4 100

範例輸出1

11

範例輸出2

4

提示

注意overflow