Cho một mảng gồm \(n\) phần tử, nhiệm vụ của bạn là chia thành \(k\) mảng con. Chi phí của mỗi mảng con là bình phương của tổng của các giá trị trong mảng con. Tổng chi phí tối thiểu là bao nhiêu nếu bạn hành động một cách tối ưu?

Input

• Dòng đầu vào đầu có hai số nguyên \(n\) và \(k\): 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, \ldots, n\)
• Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng

Constraints

• \(1 \leq k \leq n \leq 3000\)
• \(1 \leq x_i \leq 10^5\)

Output

• In một số nguyên: tổng chi phí tối thiểu

Example

8 3
2 3 1 2 2 3 4 1

110