Mong ước của anh ...

Chắc các bạn còn nhớ bài toán Mong ước của tớ trong contest Thử thách của Luna. Hôm nay chúng ta có một phiên bản khác. Sau những ngày rèn luyện với ICPC thì anh Phú đã về trên núi để tu luyện thêm cùng đàn cầy tơ. Anh có tất cả ~L~ em cầy tơ mà mỗi em có một độ ngon, à nhầm, cân nặng nhất định, là một số nguyên dương. Anh cần chia chúng thành ~G~ nhóm mà mỗi nhóm có số cầy tùy ý rồi nhốt vào chuồng để các em không chạy lung tung. Chi phí để nuôi mỗi chuồng bằng với tổng cân nặng nhân với số con trong chuồng đó. Chẳng hạn nếu có một chuồng có các em cầy có cân nặng: ~1,2,3~ thì chi phí nuôi là ~3(1+2+3)=18.~ Hãy giúp anh Phú nghiên cứu tìm ra cách chia sao cho chi phí nuôi nhốt là ít nhất nhé, chú ý rằng các em cầy phải chia trọn vẹn vào chuồng chứ không được cắt ra thành nhiều phần.

Input

Dòng đầu tiên gồm số nguyên dương ~L, G~ với ~1 \le L \le 8000~ và ~1 \le G \le 800.~

Mỗi dòng tiếp theo trong ~L~ dòng, ta có một số nguyên dương không vượt quá ~10^9.~

Output

Đáp số của bài toán.

Sample input

6 3
11
11
11
24
26
100

Sample output

299

Giải thích cách chia tối ưu là ~(11,11,11), (24,26), (100)~ với chi phí ~3.(11+11+11) + 2.(24+26)+ 1.100=299.~