Tỉ phú Vương dự định sẽ xây một thủy cung thu hút khách du lịch. Để thực hiện dự định đó, ông ta đã mua \(n\) chú cá và \(m\) bể thủy sinh. Chú cá thứ \(i\) có sức mạnh là \(a_i\).

Vương cần phải quyết định xem, với mỗi chú cá thì ông sẽ đặt vào bể thủy sinh nào. Tuy nhiên, việc này không hề đơn giản, khi ông sẽ phải xem xét đến giới hạn không gian và khả năng kìm hãm sự phát triển lẫn nhau giữa những chú cá trong cùng một bể. Sau những tính toán kĩ lưỡng, ông đã ước tính rằng mức độ bất ổn của mỗi chú cá sẽ bằng tổng sức mạnh của các chú cá nằm cùng bể thủy sinh với chú cá đó (bao gồm cả bản thân chú cá đó).

Yêu cầu: Hãy giúp tỉ phú Vương đặt các chú cá vào các bể thủy sinh sao cho tổng độ bất ổn của các chú cá là nhỏ nhất.

Input

• Dữ liệu vào từ file văn bản AQUARIUM.INP:
  • Dòng đầu tiên gồm hai số nguyên \(n\) và \(m\) (\(1 \le m \le n \le 2000\)) cho biết số chú cá và số bể thủy sinh.
  • Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) cho biết sức mạnh của các chú cá.
• Hai số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra file văn bản AQUARIUM.OUT một số nguyên duy nhất là tổng độ bất ổn nhỏ nhất của các chú cá.

Example

6 3
9 2 11 3 5 8

75

4 4
10 20 30 40

100

Hạn chế

• Có \(20\%\) số test ứng với \(n \le 8\).
• Có \(20\%\) số test khác ứng với \(n \le 15\).
• Có \(20\%\) số test khác ứng với \(m = 2\).
• Có \(30\%\) số test khác ứng với \(n \le 100\).
• \(10\%\) số test còn lại không có giới hạn gì thêm.