Su kem ăn thì rất ngon, nhưng ăn nhiều quá thì lại không tốt...

Sau bao ngày tìm tồi nghiên cứu Chưng đã tìm ra cho một mình cách ăn so healthy đối với những chiếc bánh su kem. Cụ thể cách ăn đó như sau: Giả sử Chưng có cho mình N chiếc bánh su kem trên bàn được đánh số từ 1 đến N và mỗi chiếc sẽ có một độ béo là x với ~1 \le x_i \le 10^6~. Để không bị béo Chưng sẽ chia những chiếc bánh này thành G đoạn liên tiếp và sẽ ăn trong G ngày. Biết rằng nếu ăn những chiếc bánh từ vị trí i đến vị trí j Chưng sẽ mập lên một lượng ~min \sum_{s = i}^{j} |x_s - v|^k~ với ~v~ là số nguyên nào đó.

Tuy tìm được cách ăn healthy trên nhưng cậu ấy lại không thể nào cưỡng lại được độ ngon của những chiếc bánh và tương lai sẽ dẫn đến việc bị bỏ rơi do mập, nên bạn hãy giúp cậu ấy tìm khối lượng tăng lên ít nhất nếu cậu ấy ăn healthy như trên trong G ngày.

Input

• Dòng đầu tiên gồm ba số nguyên ~N, G, K~ với ~1 \le N, G \le 2.10^3~ , ~1 \le K \le 2~.

• ~N~ số tiếp theo là độ béo của từng chiếc bánh với ~1 \le x_i \le 10^6~. Trong đó ~x_i \lt x_{i+1}~, ~0 \le i\lt N~

Output

Một dòng duy nhất là khối lượng tối thiểu mà Chưng sẽ tăng lên khi ăn trong ~G~ ngày.

Sample Input 1

5 2 1
1 2 3 4 5

Sample Output 1

3

Giải thích:

Ngày đầu tiên Chưng sẽ ăn các chiếc bánh từ vị trí ~1~ đến ~3.~

Ngày thứ hai Chưng sẽ ăn những chiếc bánh còn lại.