Description

一个序列的第1,3,5...项被称作奇数项，第2,4,6...项被称作偶数项。一个序列A[1..n]被称作ZigZag序列当且仅当以下两个条件中的一个（或两个）成立： 1）除了首项，所有的奇数项都比它的前项小且所有的偶数项都比它的前项大。 2）除了首项，所有的奇数项都比它的前项大且所有的偶数项都比它的前项小。一个序列A[1..n]被称作K凹凸序列当且仅当它的最长ZigZag子序列（不一定是连续子序列）的长度不超过K。现在有一个序列A[1..n]，每次可以花费1的代价使得A中的某一项增加或减少1。我们的目的是花费最少的代价让它成为K凹凸序列。

Input

输入的第一行包含两个正整数，分别表示数列A[1..N]的长度N和K。接下来的N行每行一个自然整数，依次表示数列的项。前1个测试点满足：K=1，N≤20000 第2~8个测试点满足：K=2，N≤20000 第9~15个测试点满足：K=3，N≤20000 第16~20个测试点满足：K≤10，N≤1000 所有测试点满足：A[i]≤50000

Output

输出一个整数，表示最小代价。

Sample Input

Sample Output

Hint

Source