Cho một mảng gồm \(n\) phần tử, nhiệm vụ của bạn là chia thành \(k\) đoạn. Chi phí của mỗi đoạn là bình phương của tổng của các giá trị trong đoạn đó.

Yêu cầu: tìm cách chia dãy gồm \(n\) phần tử thành \(k\) đoạn sao cho tổng chí phí của \(k\) đoạn là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(𝑛\) và \(𝑘 (1 ≤ 𝑘 ≤ 𝑛 ≤ 3000)\): các phần tử của mảng và số lượng mảng con. Các phần tử của mảng được đánh số \(1,2,...,𝑛\).

• Dòng thứ hai có \(𝑛\) số nguyên \(x_1,x_2,...,x_n.(1 ≤ x_i ≤ 10^5)\).

Output

• Tổng chi phí ít nhất cần tìm.

Sample INput

8 3 
2 3 1 2 2 3 4 1

Sample Output

110

Ràng buộc

• Subtask 1: \(n, k ≤ 100\)

• Subtask 2: \(n, k ≤ 3000\)