Given a non-decreasing sequence $a_1, a_2, \ldots, a_n$ of $n$ numbers. The cost of a consecutive segment $l, r$ is defined as the minimum value of $\sum_{i = l}^{r} |a_i - z|^k$ where $z$ is an integer. Divide the sequence into $d$ consecutive segments such that the total cost of the segments is minimized.
### Input
- The first line contains three positive integers $n, d, k.$
- The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n.$
### Output
- Print the result of the problem.
### Constraints
- $ 1 \le d \le n \le 2000.$
- $1 \le a_1,a_2,...,a_n \le 10^6.$
- $1 \le k \le 2.$
### Example
Input
```
5 1 2
1 2 3 4 5
```
Output
```
10
```
Input
```
3 1 1
1 2 3
```
Output
```
2
```
