Pagoda

Chính quyền địa phương cần xây dựng cầu thang đến một ngôi chùa trên đỉnh núi. Dọc theo sườn núi có \(N\) vị trí với các độ cao tương ứng là \(a_1, a_2, \ldots, a_n\). Dãy độ cao này là một dãy không giảm, tức là \(a_i \le a_{i+1}\) với mọi \(0 < i < N\).

Giá để xây dựng một đoạn cầu thang từ vị trí \(i\) đến vị trí \(j\) được xác định bởi công thức:

Trong đó, \(v\) là độ cao chuẩn được chọn cho đoạn cầu thang đó, và \(k\) là một hằng số cho trước (\(k=1\) hoặc \(k=2\)).

Để tăng tốc độ xây dựng, chính quyền quyết định giao việc cho \(G\) nhà thầu. \(N\) vị trí sẽ được chia thành \(G\) đoạn liên tiếp khác nhau, và mỗi nhà thầu sẽ chịu trách nhiệm xây dựng một đoạn.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa ba số nguyên \(N, G, k\) (\(1 \le N \le 2000\), \(1 \le G \le N\), \(1 \le k \le 2\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\), \(a_i \le a_{i+1}\)), là độ cao của các vị trí.

Output

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để xây dựng cầu thang.

Example

5 3 2
1 3 4 6 7

2

5 3 1
1 3 4 6 7

2

Scoring

• Subtask \(1\) (\(25\%\) số điểm) : \(N \leq 20\).
• Subtask \(2\) (\(25\%\) số điểm) : \(N \leq 200\).
• Subtask \(3\) (\(25\%\) số điểm) : \(k = 1\).
• Subtask \(4\) (\(25\%\) số điểm) : không có ràng buộc nào thêm.