Khi xây dựng cầu thang đến các ngôi chùa nổi tiếng ở trên đỉnh núi, Chính quyền địa phương đã xác định ~N~ vị trí dọc theo sườn núi với các độ cao ~a_1, a_2, …, a_n~. Trong đó ~a_i< a_{i+1}~ và ~0< i< N~.

Giá để xây dựng cầu thang từ vị trí ~i~ đến vị trí ~j~ là: ~\min_{v\in Z}\sum_{s=i}^{j} |a_s-v|^k~

Để đẩy nhanh quá trình xây dựng cầu thang từ vị trí ~1~ đến vị trí ~N~, chính quyền địa phương đã quyết định giao việc cho ~G~ nhà xây dựng để xây dựng cầu thang song song nhau. Với ~N~ vị trí sẽ được chia thành ~G~ đoạn khác nhau và mỗi đoạn sẽ được phụ trách bởi một nhà thầu xây dựng khác nhau. Với ~G~ nhà thầu xây dựng (~0 < G \le N~) bạn hãy phân chia để ~G~ nhà thầu xây dựng cây cầu với tổng chi phí bé nhất.

Dữ liệu vào

• Dòng ~1~ ghi ba số nguyên ~N, G, K~ (~1\le N \le 2000~, ~1 \le G\le N, 1 \le k \le 2~).
• Dòng ~2~ ghi dãy số nguyên ~a_1 , a_2, … ,a_n~ (~1\le a_i \le 10^6~,~a_i \le a_{i+1} \,∀0< i < N~) các vị trí cần xây dựng.

Dữ liệu ra

• Giá trị xây dựng bé nhất

Ví dụ

Dữ liệu vào

5 1 1
1 2 3 4 5

Dữ liệu ra

6