JOI (Juicy Orange Industry) chuẩn bị đóng gói và vận chuyển \(N\) quả cam đang nằm trên băng chuyền, được đánh số từ 1 đến \(N\) theo thứ tự từ đầu băng chuyền. Kích thước quả cam \(i\) là \(A_i\).

Các quả cam phải được đóng vào một số hộp theo thứ tự. Mỗi hộp chỉ chứa một đoạn liên tiếp và chứa nhiều nhất \(M\) quả. Nếu một hộp chứa \(s\) quả, trong đó kích thước lớn nhất là \(a\) và nhỏ nhất là \(b\), chi phí của hộp là

\(K\) là chi phí cố định, như nhau với mọi hộp. Hãy tìm tổng chi phí nhỏ nhất để đóng gói toàn bộ cam.

Dữ liệu vào

• Dòng đầu chứa \(N,M,K\).
• \(N\) dòng tiếp theo: dòng \(i\) chứa \(A_i\).

Dữ liệu ra

In ra tổng chi phí nhỏ nhất.

Ràng buộc

• \(1\le N\le20000\).
• \(1\le M\le1000\) và \(M\le N\).
• \(0\le K\le10^9\).
• \(1\le A_i\le10^9\).

Phân nhóm

• Nhóm 1 (20 điểm): \(N\le20\).
• Nhóm 2 (50 điểm): \(N\le2000\), \(M\le100\).
• Nhóm 3 (30 điểm): không có ràng buộc bổ sung.

Ví dụ

6 3 6
1
2
3
1
2
1

21

16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19

164

16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12

177

10 1 1000000000
1
1
1
1
1
1
1
1
1
1

10000000000

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 1.