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;
int n,k;
long long s[20];
long long t[20];
long long sum;
void dfs(int x,int y,long long z)
{
	if(y==k)
	{
		if(sum>z)
		sum=z;
		return;
	}
	for(int i=x+1;i<n;i++)
	{
		int res=0;
		for(int j=0;j<=x;j++)
		{
			if(t[j]>res)
			res=t[j];
		}
		if(t[i]>res)
		dfs(i,y+1,z);
		else 
		{
			int c=t[i];
			t[i]=res+1;
		    dfs(i,y+1,z+res+1-c);
		    t[i]=s[i];
	    }
	}
}
int main(){
	while(scanf("%d%d",&n,&k)==2)
	{
		sum=20000000000;
		for(int i=0;i<n;i++)
		{
			scanf("%lld",&s[i]);
			t[i]=s[i];
		}
		for(int i=0;i<n;i++)
		dfs(i,1,0); 
		printf("%lld\n",sum);
	}
} 