#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,x;
int c[101];
int a[101][101];
int sum[101];
int ans=0x7fffffff;
int main()
{
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=(1<<n);i++)
	{
		int sum1=0;
		for(int j=1;j<=m;j++)
			sum[j]=0;
		for(int j=1;j<=n;j++)
			if(i&(1<<(j-1))) {
				sum1+=c[j];
				for(int k=1;k<=m;k++)
					sum[k]+=a[j][k];
			}
		bool f=0;
		for(int j=1;j<=m;j++)
			if(sum[j]<x) f=1;
		if(!f) ans=min(ans,sum1);
	}
	printf("%d",ans==0x7fffffff ? -1 : ans);
	return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

Constraints

* All values in input are integers.
* 1\leq N, M\leq 12
* 1\leq X\leq 10^5
* 1\leq C_i \leq 10^5
* 0\leq A_{i, j} \leq 10^5

Input

Input is given from Standard Input in the following format:


N M X
C_1 A_{1,1} A_{1,2} \cdots A_{1,M}
C_2 A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
C_N A_{N,1} A_{N,2} \cdots A_{N,M}


Output

If the objective is not achievable, print `-1`; otherwise, print the minimum amount of money needed to achieve it.

Examples

Input

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9


Output

120


Input

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5


Output

-1


Input

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2


Output

1067

### Response

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,x;
int c[101];
int a[101][101];
int sum[101];
int ans=0x7fffffff;
int main()
{
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=(1<<n);i++)
	{
		int sum1=0;
		for(int j=1;j<=m;j++)
			sum[j]=0;
		for(int j=1;j<=n;j++)
			if(i&(1<<(j-1))) {
				sum1+=c[j];
				for(int k=1;k<=m;k++)
					sum[k]+=a[j][k];
			}
		bool f=0;
		for(int j=1;j<=m;j++)
			if(sum[j]<x) f=1;
		if(!f) ans=min(ans,sum1);
	}
	printf("%d",ans==0x7fffffff ? -1 : ans);
	return 0;
}
```