Problem:


Score : 300 points

Problem

Takahashi, who is a novice in competitive programming, wants to learn M algorithms.
Initially, his understanding level of each of the M algorithms is 0.

Takahashi is visiting a bookstore, where he finds N books on algorithms.
The i-th book (1\leq i\leq N) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j-th algorithm will increase by A_{i,j} for each j (1\leq j\leq M).
There is no other way to increase the understanding levels of the algorithms.

Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.

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.

Sample Input 1

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

Sample Output 1

120

Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.

Sample Input 2

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

Sample Output 2

-1

Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.

Sample Input 3

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

Sample Output 3

1067



Sample input:
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9


Sample output:
120

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())


cal = [list(map(int,input().split())) for _ in range(n)]


from itertools import product
ans = float("inf")

for bits in product([0, 1], repeat=n):
    ansl = [0 for _ in range(m+1)]
    for idx, bit in enumerate(bits):
        for i in range(m+1):
            ansl[i] += bit * cal[idx][i]
    for i in range(1, m+1):
        if ansl[i] < x:
            break
    else:
        ans = min(ansl[0], ans)
    continue
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations

    INF = 1 << 30

    N, M, X = map(int, input().split())

    book = []
    for _ in range(N):
        c, *a = map(int, input().split())
        book.append((c, a))

    ans = INF
    for take in range(1, N + 1):
        for comb in combinations(book, r=take):
            cost = 0
            know = [0] * M
            for c, a in comb:
                cost += c
                for i, x in enumerate(a):
                    know[i] += x
            if all(x >= X for x in know) and ans > cost:
                ans = cost

    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M, X = map(int, input().split())
CA = [[int(i) for i in input().split()] for _ in range(N)]

ret = float('inf')
for mask in range(1 << N) :
  tot = [0] * (M + 1)
  for i in range(N) :
    if mask & (1 << i) :
      for j in range(M + 1) :
        tot[j] += CA[i][j]
        
  if min(tot[1:]) >= X :
    ret = min(ret, tot[0])
    
if ret == float('inf') :
  print(-1)
else :
  print(ret)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]

ans = float("INF")

for i in range(2**n):
    count = [0]*m
    c = 0
    for j in range(n):
        if (i >> j) & 1:
            c += l[j][0]
            for k in range(1,m+1):
                count[k-1] += l[j][k]
    check = True
    for j in count:
        if j < x:
            check = False
            break
    if check:
        ans = min(ans,c)
if ans == float("INF"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(n)]
ans = float("inf")
for i in range(1<<n):
    cnt = [0]*m
    cost = 0
    for j in range(n):
        if i >> j & 1:
            cost += c[j][0]
            for k in range(1,m+1):
                cnt[k-1] += c[j][k]
    for j in range(m):
        if cnt[j] < x: break
    else:
        ans = min(cost,ans)
print(ans if ans != float("inf") else -1)

Submission status: Accepted

Solution code:
n,m,x = list(map(int,input().split()))
c = [[] for i in range(n)]

for i in range(n):
    c[i] = list(map(int,input().split()))

check = [0]*n

def dekiru(ls):
    hantei = [0]*m
    for i in range(n):
        if check[i] == 1:
            for j in range(m):
                hantei[j] += c[i][j+1]
    for i in range(m):
        if hantei[i] < x:
            return False
    return True

ans = 10000000000000000000000

def solv(idx):
    global ans
    if idx == n:
        kane = 0
        for i in range(n):
            if check[i] == 1:
                kane += c[i][0]
        if dekiru(check):
            ans = min(ans,kane)
        return



    check[idx] = 0
    solv(idx+1)
    check[idx] = 1
    solv(idx+1)

solv(0)
print(ans if ans != 10000000000000000000000 else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

n,m,x=map(int,input().split())
ca=[]
for i in range(n):
    ca.append(list(map(int,input().split())))

ans=10**10
for i in range(1<<n):
    t=[0]*m
    kai=0
    for j in range(n):
        if i&(1<<j)!=0:
            for k in range(m):
                t[k]+=ca[j][k+1]
            kai+=ca[j][0]
    if min(t)>=x:
        ans=min(ans,kai)
if ans==10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m, x = map(int, input().split())
    c = []
    a = []
    for _ in range(n):
        ac = list(map(int, input().split()))
        c.append(ac[0])
        a.append(ac[1:])
    answer = float("inf")
    for i in range(1, pow(2, n)):
        now = 0
        all_c = [0 for _ in range(m)]
        for j in range(n):
            if (i >> j) & 1:
                for k in range(m):
                    all_c[k] += a[j][k]
                now += c[j]
        if all(all_c[j] >= x for j in range(m)):
            answer = min(answer, now)
    print(answer if answer < float("inf") else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def make_bit(n):
    bit = []
    for i in range(2**n):
        bit.append(bin(i)[2::])
    i = 0
    while i < len(bit):
        while len(bit[i]) < len(bin(2**n-1)[2::]):
            bit[i] = "0" + bit[i]
        i += 1

    return bit

n, m, X = map(int, input().split())
c = []
a = []
for i in range(n):
    ca = list(map(int, input().split()))
    c.append(ca[0])
    a.append(ca[1:])

ptarn = make_bit(n)
ans = 10 ** 10
for i in ptarn:
    money = 0
    x = [0 for _ in range(m)]
    for j in range(n):
        if i[j] == "1":
            money += c[j]
            for k in range(m):
                x[k] += a[j][k]

    if min(x) >= X:
        ans = min(ans, money)

if ans == 10 ** 10:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

n,m,x = map(int, input().split())
a = []
c = []
for i in range(n):
    cc, *aa = map(int, input().split())
    a.append(aa)
    c.append(cc)

ans = float("inf")
q = list(range(n))
for i in range(1, n+1):
    for l in combinations(q, i):
        state = [0]*m
        score = 0
        for j in l:
            score += c[j]
            for k in range(m):
                state[k] += a[j][k]
        if all(j>=x for j in state):
            ans = min(ans, score)

if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,m,x = get_nums_l()

books = [ get_nums_l() for _ in range(n)]

ans = INF

for bits in range(2 ** n):
    skills = [0] * (m)
    cost = 0
    for i in range(n):
        if 2**i & bits != 0:
            cost += books[i][0]
            for j in range(m):
                skills[j] += books[i][j+1]
    if min(skills) >= x:
        ans = min(ans, cost)

print(-1 if ans==INF else ans)

Submission status: Accepted

Solution code:
N,M,X = map(int ,input().split())
ls = []
for i in range(N):
  C,*A = map(int, input().split())
  ls.append((C,A))
ans = 10**10
for i in range(2**N):
  used = [0]*M
  m = 0
  for j in range(N):
    if i%2==0:
      C,A = ls[j]
      m += C
      for h in range(M):
        used[h] += A[h]
    i >>= 1
  if all(c>=X for c in used):
    ans = min(ans,m)
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def is_nth_bit_set(x, n):
    if x & (1 << n):
        return True
    else:
        return False


def main():
    N, M, X = map(int, input().split())
    A = [0] * M
    C = []
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        C.append(a[0])
        A.append(a[1:])

    ans = INF
    for pattern in range(2 ** N):
        money = 0
        status = [0] * M
        for i in range(N):
            if is_nth_bit_set(pattern, i):
                money += C[i]

                for j in range(M):
                    status[j] += A[i][j]

        for i in range(M):
            if status[i] < X:
                break
        else:
            if money < ans:
                ans = money

    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, X = map(int, input().split())

ans = 10**9

price = []
a = []
for _ in range(n):
    c = [int(x) for x in input().split()]
    price.append(c[0])
    a.append(c[1:])

for i in range(1 << n):
    l = [0]*m
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            tmp += price[j]
            for x in range(m):
                l[x] += a[j][x]
    if all(x >= X for x in l):
        ans = min(ans, tmp)

print(-1 if ans == 10**9 else ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M, X = map(int, rl().split())
    C, A = [0] * N, [[] for _ in range(N)]
    for i in range(N):
        C[i], *Ai = map(int, rl().split())
        A[i] = Ai
    
    ans = 10 ** 18
    for s in range(1 << N):
        b = [0] * M
        c = 0
        for i in range(N):
            if s >> i & 1:
                c += C[i]
                for j in range(M):
                    b[j] += A[i][j]
        flg = True
        for i in range(M):
            if b[i] < X:
                flg = False
                break
        if flg:
            ans = min(ans, c)
    print(ans if ans != 10 ** 18 else -1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N,M,X = map(int,input().split())
    book = []
    for _ in range(N):
        A = list(map(int,input().split()))
        cost = A[0]
        book.append((cost,A[1:]))
    
    ans = INF
    for bit in range(1<<N):
        ret = 0
        understand = [0] * M
        for i in range(N):
            if (bit>>i)&1:
                cost,A = book[i]
                ret += cost
                for j in range(M):
                    understand[j] += A[j]
        flag = True
        for j in range(M):
            if understand[j] < X:
                flag = False
                break
        if flag:
            ans = min(ans,ret)
    print(ans if ans < INF else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
books = []

for i in range(n):
    line = list(map(int, input().split()))
    c, a = line[0], line[1:]
    books.append((c, a))

ans = 1e+10
for item in itertools.product([0, 1], repeat=n):
    understand = [0] * m
    cost = 0
    for idx, buy in enumerate(item):
        if buy:
            c, a = books[idx]
            cost += c
            for i in range(m):
                understand[i] += a[i]
    if min(understand) >= x:
        ans = min(ans, cost)

print(ans if ans != 1e+10 else -1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
ans = []
for i in range(2 ** n):
    price = 0
    und = [0 for _ in range(m)]
    for j in range(n):
        if (i >> j) & 1:
            price += c[j][0]
            for k in range(m):
                und[k] += c[j][k+1]
    if all(und[i] >= x for i in range(m)):
        ans.append(price)

if ans == []:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
CA = [list(map(int,input().split())) for i in range(N)]

ans = float('inf')
for b in range(1<<N):
    arr = [0] * (M+1)
    for i in range(N):
        if b&(1<<i)==0: continue
        for j,a in enumerate(CA[i]):
            arr[j] += a
    if all(a >= X for a in arr[1:]):
        ans = min(ans, arr[0])
print(-1 if ans==float('inf') else ans)

Submission status: Accepted

Solution code:
ans = float("inf")
N,M,X = map(int,input().split())
C = []
A = []
for i in range(N):
    c,*a = map(int,input().split())
    C.append(c)
    A.append(a)
for i in range(pow(2,N)):
    n = i
    L = []
    for j in range(N):
        L.append(n%2)
        n//=2
    cost = 0
    S = [0]*M
    for j in range(N):
        if L[j]:
            cost+=C[j]
            for k in range(M):
                S[k]+=A[j][k]
    if min(S)>=X:
        ans = min(ans,cost)
if ans==float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
def main():
    N,M,X=map(int, input().split())
    CA=[list(map(int, input().split())) for _ in range(N)]
    ans=float("inf")
    for p in product((False, True), repeat=N):
        res=[0]*(M+1)
        for pp,ca in zip(p,CA):
            if pp:
                for i in range(M+1):
                    res[i] += ca[i]
        if all(res[i]>=X for i in range(1,M+1)):
            ans=min(ans, res[0])
    if ans>=10**9:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, x = [int(x) for x in input().split()]
c = [[int(x) for x in input().split()] for _ in range(n)]
ans = float('inf')
for s in range(1 << n):
    if all(sum(c[i][j] for i in range(n) if s & (1 << i)) >= x for j in range(1, m + 1)):
        ans = min(ans, sum(c[i][0] for i in range(n) if s & (1 << i)))
print(ans if ans != float('inf') else -1)

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for i in range(N)]

re=10**18
for i in range(2**N):
    mlst=[0 for i in range(M)]
    lst=[i>>m&1 for m in range(N)]
    #print(lst)
    value=0
    for n in range(N):
        if lst[n]:
            for m in range(M):
                mlst[m]+=CA[n][m+1]
            value+=CA[n][0]
    for m in range(M):
        if mlst[m]<X:
            break
    else:
        #print(mlst,value)
        re=min(re,value)

if re==10**18:
    print(-1)
else:
    print(re)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(n)]

ans = 1234567890123

for bit in range(1<<n):
    syu = [0]*m
    cost = 0
    for i in range(n):
        if (bit>>i)&1:
            cost += ca[i][0]
            for j in range(1,m+1):
                syu[j-1] += ca[i][j]
    ok = True
    for i in range(m):
        if syu[i] < x:
            ok = False

    if ok:
        ans = min(ans,cost)
print(ans if ans != 1234567890123 else -1)

Submission status: Accepted

Solution code:
import os

import itertools
import sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, X = list(map(int, sys.stdin.buffer.readline().split()))
A = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

A = np.array(A, dtype=int)
mat = A[:, 1:]
C = A[:, 0]

ans = INF
for choices in itertools.product((True, False), repeat=N):
    choices = np.array(list(choices), dtype=bool)
    if np.all(mat[choices, :].sum(axis=0) >= X):
        ans = min(ans, C[choices].sum())
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
book=[[] for i in range(N)]
for i in range(N):
    book[i]=list(map(int,input().split()))

ans=float("inf")
def dfs(num,table,cost):
    global ans
    if num==N:
        for i in range(M):
            if X>table[i]:
                break
        else:
            ans=min(ans,cost)
    else:
        table2=[table[i]+book[num][i+1] for i in range(M)]
        dfs(num+1,table2,cost+book[num][0])
        dfs(num+1,table,cost)

dfs(0,[0]*M,0)
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, X = MAP()
CA = [LIST() for _ in range(N)]

ans = INF
for x in product([0, 1], repeat=N):
	s = np.zeros((M, ))
	tmp = 0
	for i in range(N):
		if x[i]:
			C, *A = CA[i]
			tmp += C
			s += np.array(A, dtype=np.int64)
	s = s.tolist()
	if all(x >= X for x in s):
		ans = min(ans, tmp)
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [list(map(int, input().split())) for i in range(N)]

ans = float('inf')
for i in range(1, 2**N):
    score = [0] * M
    cost = 0
    for j in range(N):
        if i >> j & 1:
            cost += C[j][0]
            for m in range(M):
                score[m] += C[j][m+1]
    
    if all([s>=X for s in score]):
        ans = min(ans, cost)

if ans < float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def saiki(count,price,lis):
    if count==N:
        judge=True
        for item in lis:
            if item<X:
                judge=False
        if judge:
            ans.append(price)
    else:
        temp=[lis[i]+note[count][i+1] for i in range(M)]
        saiki(count+1,price,lis)
        saiki(count+1,price+note[count][0],temp)

N,M,X=map(int,input().split())

note=[]
for _ in range(N):
    note.append(list(map(int,input().split())))

ans=[]
saiki(0,0,[0]*M)

print(min(ans) if len(ans)!=0 else -1)

Submission status: Accepted

Solution code:
n, m, x = [int(i) for i in input().split()]
cc = []
aa = []
for _ in range(n):
    c, *a = [int(i) for i in input().split()]
    cc.append(c)
    aa.append(a)
ans = 10 ** 18
for i in range(2 ** n):
    ri = [0] * m
    co = 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            co += cc[j]
            for k in range(m):
                ri[k] += aa[j][k]
    
    for j in ri:
        if j < x:
            break
    else:
        ans = min(ans, co)

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N, M, X = map(int, input().split())
books = []
for _ in range(N):
	C, *l = map(int, input().split())
	books.append((C, l))

best = None
for bs in range(1, 2 ** N):
	lev = [0] * M
	pri = 0
	for j in range(N):
		if bs & (1 << j) == 0: continue
		pri += books[j][0]
		for k, v in enumerate(books[j][1]):
			lev[k] += v
	if all(v >= X for v in lev):
		if best is None or pri < best:
			best = pri
print(-1 if best is None else best)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ls = [list(map(int,input().split())) for i in range(n)]
ans = 10**18
for i in range(2**n):
  uds = [0]*m
  cost = 0
  for j in range(n):
    if i&1<<j:
      for k in range(m):
        uds[k] += ls[j][k+1]
      cost += ls[j][0]
  if min(uds) >= x:
    ans = min(ans,cost)
if ans == 10**18:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
B=[list(map(int,input().split())) for i in range(N)]
ANS=1<<60
for i in range(1<<N):
    SCORE=[0]*M
    MONEY=0
    for j in range(N):
        if (1<<j) & i != 0:
            MONEY+=B[j][0]
            for k in range(M):
                SCORE[k]+=B[j][k+1]
    if min(SCORE)>=X:
        ANS=min(ANS,MONEY)
if ANS==1<<60:
    print(-1)
else:
    print(ANS)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M,X=map(int,input().split())
    C=[]
    for i in range(N):
        C.append(list(map(int,input().split())))
    ans=INF
    for i in range(2**N):
        l=[0]*M
        c=0
        for j in range(N):
            if (i>>j)&1:
                c+=C[j][0]
                for k in range(M):
                    l[k]+=C[j][k+1]
        if min(l)>=X:
            ans=min(ans,c)
    if ans==INF:
        print(-1)
    else:
        print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]


ans = float('inf')
for i in range(2 ** n):
    cost = 0
    skills = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            cost += ca[j][0]

            for k in range(m):
                skills[k] += ca[j][k + 1]

    f = True
    for k in range(m):
        if skills[k] < x:
            f = False

    if f:
        ans = min(ans, cost)

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0] * N
A = [[0] * M for _ in range(N)]
for i in range(N):
    C[i], *A[i] = map(int, input().split())
ans = float('inf')
for bit in range(1 << N):
    score = [0] * M
    price = 0
    for i in range(N):
        if bit >> i & 1:
            price += C[i]
            for j in range(M):
                score[j] += A[i][j]
    if all(s >= X for s in score):
        ans = min(ans, price)
print(ans if ans < float('inf') else -1)

Submission status: Accepted

Solution code:
from collections import *

N, M, X = map(int, input().split())
CA = [tuple(map(int, input().split())) for _ in range(N)]
ans = 10**18

for S in range(2**N):
    ans_cand = 0
    now = [0]*M
    
    for i in range(N):
        if (S>>i)&1:
            ans_cand += CA[i][0]
            
            for j in range(1, M+1):
                now[j-1] += CA[i][j]
    
    if min(now)>=X:
        ans = min(ans, ans_cand)

if ans==10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m, x = map(int,input().split())
C = [list(map(int,input().split())) for i in range(n)]
ans = float("inf")
for i in range(2**n):
    R = [0] * m
    ib = format(i, "b").zfill(n)
    v = 0
    for j in range(n):
        if ib[j] == "1":
            for k in range(m):
                R[k] += C[j][k+1]
            v += C[j][0]
    
    if min(R) >= x:
        ans = min(ans, v)

if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    m, n, x = map(int, input().split())
    CA = [list(map(int, input().split())) for _ in range(m)]

    res = INF
    for U in range(1 << m): # 使う参考書を全探索
        cost = 0
        total = [0] * n
        for i in range(m):
            if (U >> i) & 1 == 0:
                continue
            c, *A = CA[i]
            cost += c
            for j, a in enumerate(A):
                total[j] += a
        if min(total) >= x:
            res = min(res, cost)

    if res == INF:
        res = -1
    print(res)
resolve()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
book = [list(map(int, input().split())) for i in range(n)]
ans = 10**18

for i in range(2**n):
    i = format(i, "0{}b".format(n))
    algo = [10**18] + [0]*m
    money = 0
    for j in range(n):
        if i[j] == "1":
            money += book[j][0]
            for k in range(m):
                algo[k+1] += book[j][k+1]
    if min(algo) >= x:
        ans = min(ans, money)

if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def ZZ(): return list(map(int, input().split()))
def Z(): return int(input())

N, M, X = ZZ()
C = []
A = []
for _ in range(N):
    tmp = ZZ()
    C.append(tmp[0])
    A.append(tmp[1:])

ans = 10 ** 100
for i in range(1 << N):
    rikai = [0] * M
    cost = 0
    for j in range(N):
        if i >> j & 1:
            cost += C[j]
            for k in range(M):
                rikai[k] += A[j][k]
    if min(rikai) >= X:
        ans = min(ans, cost)

if ans == 10 ** 100: ans = -1
print(ans)

Submission status: Accepted

Solution code:

N,M,X = map(int,input().split())

C = []

A = []

for i in range(N):

    lis = list(map(int,input().split()))
    C.append(lis[0])
    A.append(lis[1:])

ans = float("inf")

for i in range(2**N):

    now = [0] * M
    ns = 0

    for j in range(N):

        if i & (2**j) > 0:
            ns += C[j]

            for k in range(M):
                now[k] += A[j][k]

    if min(now) >= X:
        ans = min(ans,ns)

if ans == float("inf"):
    print (-1)
else:
    print (ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, M, X = map(int, input().split())
    info = []
    for _ in range(N):
        info.append(list(map(int, input().split())))

    ans = 10**10
    for i in range(2**N):
        skill = [0] * M
        price = 0
        for j in range(N):
            if i>>j&1:
                price += info[j][0]
                for k in range(1, M+1):
                    skill[k-1] += info[j][k]
        ok = 1
        for m in range(M):
            if skill[m] < X:
                ok = 0
                break
        if ok:
            ans = min(ans, price)
    if ans == 10**10:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from copy import deepcopy

N, M, X = [int(i) for i in input().split()]

CAS = [[int(i) for i in input().split()] for _ in range(N)]


ok = False
mi = [float('inf'), *[0]*(M-1)]

fs = '{:0' + str(M) + 'b}'

for i in range(2**N):
  s = fs.format(i)
  t = [0]*M
  for i, f in enumerate(s):
    if f == '1':
      t = [a+b for a, b in zip(CAS[i], t)]

  if all(a >= X for a in t[1:]) and mi[0] > t[0]:
    mi = t
    ok = True


if ok:
  print(mi[0])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
n,m,x=[int(i) for i in input().split()]
c=[]
arr=[[] for i in range(n)]
for i in range(n):
    l=[int(i) for i in input().split()]
    c.append(l[0])
    arr[i]=l[1:]

inf=10**18
ans=inf

limit=2**n
for bit in range(1,limit):
    sum=[0 for i in range(n)]
    cost=0
    for i in range(n):
        if (1<<i & bit):
            cost+=c[i]
            for j in range(m):
                sum[j]+=arr[i][j]
    flag=1
    for i in range(m):
        if sum[i]<x:
            flag=0
            break
    if flag==0:
        continue
    ans=min(ans,cost)
if ans!=inf:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n,m,x=[int(i) for i in input().split()]
c=[]
arr=[[] for i in range(n)]
for i in range(n):
    l=[int(i) for i in input().split()]
    c.append(l[0])
    arr[i]=l[1:]

inf=10**18
ans=inf

limit=2**n
for bit in range(1,limit):
    sum=[0]*n
    cost=0
    for i in range(n):
        if (1<<i & bit):
            cost+=c[i]
            for j in range(m):
                sum[j]+=arr[i][j]
    flag=1
    for i in range(m):
        if sum[i]<x:
            flag=0
            break
    if flag==0:
        continue
    ans=min(ans,cost)
if ans!=inf:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, M, X = [int(i) for i in input().split()]
CA = []
for i in range(N):
    CA.append([int(j) for j in input().split()])
#print(CA)
mcost = 10**10


for i in range(2**N):
    learn = [0]*M
    cost = 0
    bn = str(bin(i))[2:].zfill(M)
    #print(bn)
    for j,b in enumerate(bn):
        if b == "1":
            cost += CA[j][0]
            for m in range(M):
                learn[m] += CA[j][m+1]
                
    learn.sort()
    if learn[0] >= X:
        mcost = min(mcost, cost)

if mcost == 10**10:
    mcost = -1

print(mcost)

Submission status: Runtime Error

Solution code:
N,M,X = map(int, input().split())
A = np.array([[int(i) for i in input().split()] for _ in range(N)])
total = np.sum(A,axis=0)
flag = True if all((a>=X  for a in total[1:])) else False
ans = total[0]

if flag:
    for i in range(1,N+1):
        for v in itertools.combinations([i for i in range(N)], i):
            B = np.array([A[j] for j in v])
            total2 = np.sum(B, axis=0)
            sabun = total-total2
            if all(a>=X for a in sabun[1:]):
                ans = min(ans, sabun[0])
print(ans if flag else -1)