Input Format


N K
a_1 a_2 a_3 ... a_N


Output Format

Print the minimum cost in one line. In the end put a line break.


Constraints

* 1 ≤ K ≤ N ≤ 15
* 1 ≤ a_i ≤ 10^9



Scoring

Subtask 1 [120 points]


* N = K

Subtask 2 [90 points]


* N ≤ 5
* a_i ≤ 7

Subtask 3 [140 points]


* There are no additional constraints.

Output Format

Print the minimum cost in one line. In the end put a line break.


Constraints

* 1 ≤ K ≤ N ≤ 15
* 1 ≤ a_i ≤ 10^9



Scoring

Subtask 1 [120 points]


* N = K

Subtask 2 [90 points]


* N ≤ 5
* a_i ≤ 7

Subtask 3 [140 points]


* There are no additional constraints.

Input Format


N K
a_1 a_2 a_3 ... a_N

Example

Input

5 5
3949 3774 3598 3469 3424


Output

1541
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
long long n,k;
long long s[20];
long long sum,cost;
void dfs(long long a,long long b,long long c)
{
	if(a==n)
	{
		if(b>=k)
		sum=min(sum,cost);
		return;
	}
	if(s[a]>c)
	{
		dfs(a+1,b+1,s[a]);
	}
	else{
		dfs(a+1,b,c);
		cost+=(c+1-s[a]);
		dfs(a+1,b+1,c+1);
		cost-=(c+1-s[a]);
	}
}
int main(){
	while(scanf("%lld%lld",&n,&k)==2)
	{
		sum=20000000000;
		//printf("%lld\n",sum); 
		cost=0;
		for(long long i=0;i<n;i++)
		scanf("%lld",&s[i]);
		dfs(1,1,s[0]); 
		printf("%lld\n",sum);
	}
	return 0;
} 