#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
using ll=long long;


int main(){
  ll n,m,x;cin>>n>>m>>x;
  vector<vector<ll>> ca(n,vector<ll>(m+1));
  for(int i=0;i<n;i++)for(int j=0;j<m+1;j++)cin>>ca[i][j];
  
  ll money=1e9;
  for(int i=0;i<(1<<n);i++){
    bitset<12> s(i);
    vector<ll> und(m+1,0);
    for(int j=0;j<n;j++)
      if(s.test(j))
        for(int k=0;k<m+1;k++)
          und[k]+=ca[j][k];
    ll mx=und[1];
    for(int j=2;j<m+1;j++)mx=min(mx,und[j]);
    if(mx>=x)money=min(money,und[0]);
  }
  if(money==1e9)cout<<-1<<endl;
  else cout<<money<<endl;
}
### Prompt

Your challenge is to write a Cpp solution to the following problem:

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<bits/stdc++.h>
#include<algorithm>
using namespace std;
using ll=long long;


int main(){
  ll n,m,x;cin>>n>>m>>x;
  vector<vector<ll>> ca(n,vector<ll>(m+1));
  for(int i=0;i<n;i++)for(int j=0;j<m+1;j++)cin>>ca[i][j];
  
  ll money=1e9;
  for(int i=0;i<(1<<n);i++){
    bitset<12> s(i);
    vector<ll> und(m+1,0);
    for(int j=0;j<n;j++)
      if(s.test(j))
        for(int k=0;k<m+1;k++)
          und[k]+=ca[j][k];
    ll mx=und[1];
    for(int j=2;j<m+1;j++)mx=min(mx,und[j]);
    if(mx>=x)money=min(money,und[0]);
  }
  if(money==1e9)cout<<-1<<endl;
  else cout<<money<<endl;
}
```