Chia dãy thành đoạn

Cho dãy gồm $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$.

Hãy chia dãy thành đúng $k$ đoạn con liên tiếp không rỗng (mỗi phần tử thuộc đúng một đoạn, các đoạn phủ kín dãy). Với mỗi đoạn, chi phí của nó bằng bình phương tổng các phần tử trong đoạn.

Hãy tìm cách chia sao cho tổng chi phí của $k$ đoạn 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 $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên — tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le k\le min(n,20)$
• $0\le a_i\le {10}^4$

Ví dụ

Ghi chú

Việc chia thành nhiều đoạn hơn luôn giúp giảm tổng bình phương, nhưng số đoạn bị cố định bằng $k$.