Huy đang sở hữu một chiếc vòng tay lấp lánh gồm ~n~ hạt pha lê quý giá. Các hạt pha lê được đánh số liên tục từ ~1~ đến ~n~. Hạt pha lê thứ ~i~ có một giá trị nguyên dương là ~a[i]~ và được xâu lại theo một sợi chỉ vô hình, tạo thành một vòng khép kín. Điều đặc biệt là chiếc vòng này không có điểm bắt đầu hay kết thúc, hạt thứ ~i~ (~1 \le i < n~) nằm bên trái hạt thứ ~i + 1~, hạt pha lê thứ ~n~ nằm bên trái hạt pha lê thứ ~1~.

Giờ đây, Huy muốn cắt một số sợi chỉ để có thể chia vòng tay pha lê thành ~k~ đoạn gồm các hạt pha lê liên tiếp nhau. Tuy nhiên, khi cắt các sợi chỉ để tạo thành một đoạn các hạt pha lê liên tiếp sẽ tiêu tốn chi phí bằng bình phương tổng các giá trị của các hạt pha lê trong đoạn. Cụ thể hơn, nếu đoạn các hạt pha lê có độ dài là ~m~ và dãy giá trị là ~b[1], b[2], \dots, b[m]~, chi phí của đoạn này bằng ~(b[1] + b[2] + \dots + b[m])^2~.

Chi phí của một cách cắt tạo thành ~k~ đoạn pha lê chính là bằng tổng chi phí của các đoạn tạo thành. Nhiệm vụ của Huy là tìm cách cắt vòng tay sao cho tổng chi phí phải trả là nhỏ nhất.

Yêu cầu: Tìm tổng chi phí tối thiểu để chia vòng tay thành ~k~ đoạn.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, k~ (~2 \le k \le n \le 1000~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a[1], a[2], \dots, a[n]~ (~1 \le a[i] \le 10^5~).

Output

• Một số nguyên duy nhất là tổng chi phí tối thiểu để chia vòng tay thành ~k~ đoạn.