題目描述

給定一個長度為 $N$ 的序列 $A$，要求你把它分成恰好 $M$ 個子段。記第 $i$ 個子段左端點為 $L[i]$，右端點為 $R[i]$，則需要滿足 $L[1] = 1, L[M] = N, R[i] + 1 = L[i + 1]$ （對於所有滿足 $1 \le i \le M$ 的 $i$）。記第 $i$ 個子 段的代價 $C[i] = (\sum^{R[i]}_{j=L[i]} A[j])^2$，你需要最小化並輸出所有子段的代價和 $S = \sum^M_{i=1} C[i]$。

輸入格式

第一行兩個正整數 $N,M$
第二行 $N$ 個正整數表示序列 $A$

輸出格式

輸出一行一個正整數表示最小的 $S$

Samples

10 3
1 1 4 5 1 4 1 9 1 9

440

提示

1 ≤ M ≤ N ≤ 2 × 10⁵ 

1 ≤ A[i] ≤ 10⁴ 

子任務

1. （30分）N ≤ 100

2. （30分）M ≤ 50

3. （40分）没有額外的約束條件。

原始資料

• Zero1 題號：b103
• Hydro 題號：Z1103
• Locale：zh_TW
• Display：open