Given an array A of n integers. The cost of a subarray Al...r is (Al−Ar)2. Your task is dividing array A in k subarrays so that the total cost is minimized.
### Input
- The first line contains two integers n,k.
- The second line contains n integer Ai.
### Output
- Print an integer is the minimum cost.
### Constraints
- 1≤n≤104.
- 1≤k≤min(100,n).
- 1≤Ai≤109.
### Example
Input:
5223154
Output:
1