Vụ nổ kinh thiên động địa từ lõi trung tâm thao túng tín hiệu tạo ra một sức công phá quá lớn, không những làm sụp đổ hoàn toàn cơ ngơi của Team Rocket mà còn làm rung chuyển dữ dội các tầng ngậm nước sâu dưới lòng đất, dẫn đến một hệ lụy vô cùng thảm khốc: phong ấn phong thủy ở tầng sâu nhất của Ruins of Alph đã bị phá vỡ hoàn toàn! Bầu trời đỏ rực lên như máu, đất đá nứt toác, và từ trong biển lửa dung nham trào dâng, Groudon - sinh vật siêu cổ đại nắm giữ sức mạnh kiến tạo lục địa và thao túng núi lửa - đã chính thức thức tỉnh sau giấc ngủ hàng ngàn năm.

Sự phẫn nộ tột độ vì bị quấy rầy của Groudon đã lập tức chẻ đôi mặt đất, tạo ra một khe nứt dung nham khổng lồ kéo dài hàng dặm, phân chia dải bình nguyên xanh tươi phía trước mặt Ash thành \(N\) khu vực liên tiếp nhau chìm trong biển lửa. Các cảm biến nhiệt trên máy đo của hệ thống liên tục nhấp nháy ánh đèn đỏ báo động, cho biết khu vực thứ \(i\) hiện đang tỏa ra một mức nhiệt độ kinh hoàng lên tới \(T_i\) độ, đủ sức thiêu rụi mọi thứ thành tro bụi.

Tình thế lúc này thực sự ngàn cân treo sợi tóc: nếu không tìm cách làm nguội dòng chảy của khe nứt này trong vòng vài phút tới, hàng ngàn tấn dung nham sẽ tràn ra ngoài, hủy diệt sinh thái của toàn bộ phần còn lại của Viridian Forest và đe dọa sinh mạng của hàng vạn sinh linh. Không chần chừ nửa giây, Ash lập tức tung quả Pokeball chứa Lapras ra ngoài, khẩn thiết yêu cầu người bạn hệ Nước/Băng của mình sử dụng chiêu thức "Tia Băng Giá Tuyệt Đối" (Sheer Cold) để dập tắt ngọn lửa địa ngục.

Tuy nhiên, việc đóng băng cả một đại dương dung nham không phải là chuyện đơn giản. Để kiểm soát luồng năng lượng khổng lồ không bị phản hệ, cậu bắt buộc phải chia \(N\) khu vực dung nham này thành đúng \(K\) đoạn liên tiếp nhau để Lapras lần lượt đóng băng từng đoạn một. Theo cơ chế vật lý phép thuật của chiêu thức này, nếu Lapras nhắm mục tiêu đóng băng một đoạn bao gồm các khu vực trải dài từ vị trí \(L\) đến vị trí \(R\), lượng sinh lực và năng lượng phép thuật mà Lapras bị rút cạn cho đoạn đó sẽ bằng bình phương của tổng nhiệt độ của tất cả các khu vực nằm trong đoạn đó: \((\sum_{i=L}^R T_i)^2\).

Suy ra, tổng năng lượng tiêu tốn của Lapras cho toàn bộ chiến dịch giải cứu này chính là tổng năng lượng làm nguội cộng dồn của cả \(K\) đoạn. Ash cần phải thiết lập một chiến thuật phân chia các khu vực thành đúng \(K\) đoạn sao cho tổng năng lượng tiêu tốn của Lapras được ép xuống mức nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le K \le N \le 10^5\); \(1 \le K \le 20\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(T_1, T_2, \dots, T_N\) (\(1 \le T_i \le 10^4\)).

Output

• In ra một số nguyên duy nhất đại diện cho mức năng lượng tiêu tốn tối thiểu của Lapras.

Example

4 2
1 2 3 4

52

5 3
4 5 1 2 3

77

3 1
10 10 10

900

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(N \le 100\), \(K \le 10\).
• Subtask \(2\) (\(30\%\) điểm): \(N \le 2000\), \(K \le 20\).
• Subtask \(3\) (\(50\%\) điểm): Không còn ràng buộc gì thêm.