Chia Mảng Thành Bình Phương

Cho một mảng gồm $n$ phần tử, hãy chia mảng thành đúng $k$ mảng con liên tiếp. Chi phí của mỗi mảng con bằng bình phương tổng các phần tử trong mảng con đó.

Tìm cách chia sao cho tổng chi phí là nhỏ nhất.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $k$.
• Dòng 2: $n$ số nguyên $x_1,x_2,\dots ,x_n$.

Dữ liệu ra

• Một số nguyên — tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le k\le n\le 3000$
• $1\le x_i\le {10}^5$

Ví dụ