Cà rốt cho thỏ

Có $n$ củ cà rốt với độ dài $a_1,a_2,\dots ,a_n$. Bạn cần cắt các củ cà rốt thành đúng $k$ khúc, sao cho mỗi khúc có độ dài là một số nguyên dương.

Thời gian để ăn một khúc cà rốt độ dài $x$ là $x^2$. Hãy cắt cà rốt sao cho tổng thời gian ăn tất cả các khúc là nhỏ nhất.

Một củ cà rốt độ dài $a$ có thể bị cắt thành nhiều khúc (tổng độ dài các khúc bằng $a$), và mỗi khúc là số nguyên dương. Mỗi củ cà rốt phải được giữ nguyên hoặc cắt thành ít nhất một khúc, và tổng số khúc trên tất cả củ cà rốt phải bằng đúng $k$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: số củ cà rốt ban đầu và số khúc cần cắt.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: độ dài các củ cà rốt.

Dữ liệu ra

In ra một số nguyên: tổng thời gian nhỏ nhất để ăn hết các khúc cà rốt.

Ràng buộc

• $1\le n\le k\le {10}^5$
• $1\le a_i\le {10}^6$
• Tổng $a_i$ ít nhất bằng $k$ (luôn có thể cắt thành $k$ khúc nguyên dương).

Ví dụ