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:
import numpy as np

_,*_t=[list(map(int,i.split())) for i in open(0)]
n=_[0]
m=_[1]
x=_[2]
t=np.array(_t)
v=9000000


def checkAchieve(nums):
  for i in range(1,m+1):
    if nums[i]<x:
      return False
  return True


tmp=np.sum(t,axis=0)
if not checkAchieve(tmp):
  print(-1)
  exit()

  
def makeBoolList(nums):
  ls=[]
  sNums=str(nums)
  for i in range(len(sNums)):
    if sNums[i]=="0":
      ls.append(False)
    else:
      ls.append(True)
  return ls


for i in range(1,2 ** n):
  sc=format(i,'b').zfill(n)
  bSc=makeBoolList(sc)
  sumPicks=np.sum(t[bSc,:],axis=0)
  if not checkAchieve(sumPicks):
    continue
  v=min(v,sumPicks[0])

  
print(v)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

result = []
adds = []
for j in range(1,n+1):
     for conb in itertools.combinations(san, j):
        result.append(list(conb)) #タプルをリスト型に変換

for i in result:
    t = np.zeros([m+1], dtype=int)
    for j in i:
        t = t + np.array(j)

    adds.append(t)

price = -1
ans = 0
for num, i in enumerate(adds):
    use = True
    for j in range(1,m+1):
        if i[j] < x:
            # print(i)
            use = False
            break

    if use:
        # print(i)
        # print(result[num])
        if price == -1 or price > i[0]:
        # if price > i[0]:
            price = i[0]
            ans = num

print(price)

Submission status: Accepted

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

import itertools
#sankouは1ずれ
sankou=[]
patterns=[]
sankoutotal=[0 for i in range(M)]
mintotal=99999999999999
for n in range(N):
    sankou.append(list(map(int,input().split())))
    for i in range(1,M+1):
        sankoutotal[i-1]+=sankou[-1][i]
#print(sankou)

nums = [0,1]
for balls in itertools.product(nums, repeat=N):
    patterns.append(balls)
    #print(balls)
for i in range(len(patterns)):
    total=0
    syutoku=[0 for i in range(M)]
    for n in range(N):
        for m in range(M):
            syutoku[m]=syutoku[m]+patterns[i][n]*sankou[n][m+1]
        total=total+patterns[i][n]*sankou[n][0]
    #print(total,syutoku)
    can=True
    for m in range(M):
        if syutoku[m] < X:
            can=False
            break
    #print(can,total,mintotal)
    if total < mintotal and can:
        mintotal=total
if mintotal==99999999999999:
    print(-1)
else:
    print(mintotal)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
text = []
ans=10000000000000
for i in range(n):
    tmp = list(map(int, input().split()))
    text.append(tmp)
for i in range(2**n):
    total = [0] * (m + 1)
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m+1):
                total[k]+=text[j][k]
    cnt=0
    for k in range(1,m+1):
        if total[k]>=x:
            cnt+=1
    if cnt==m:
        ans=min(ans,total[0])
if ans==10000000000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
N,M,X = map(int, input().split())
matrix = np.array([list(map(int, input().split())) for _ in range(N)])

min_price = 1e9
for n in range(N):
  for texts in combinations(matrix, n+1):
    summation = np.sum(texts, axis=0)
    price = summation[0]
    if all(summation[1:] >= X):
      min_price = min(price, min_price)

print(min_price if min_price < 1e9 else -1)

Submission status: Accepted

Solution code:
def can_reach_the_goal(u, x):
    return min(u) >= x

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

c = []
a = []
for i in range(n):
    ca = [int(row) for row in input().split()]
    c.append(ca[0])
    a.append(ca[1:])

INF = 10**7
min_cost = INF
for k in range(2**n):
    purchase = [True if c == '1' else False for c in list(format(k, '0{}b'.format(n)))]
    cost = 0
    u = [0]*m
    for i in range(n):
        cost += c[i] if purchase[i] else 0
        for j in range(m):
            u[j] += a[i][j] if purchase[i] else 0

    if can_reach_the_goal(u, x) and cost < min_cost:
        min_cost = cost

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

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 10**7
for i in range(2**n):
    select_list = list(map(int, format(i, '0'+str(n)+'b')))
    tmp = []
    r = np.array([x] * m)
    money = 0
    c = True
    for i, ca in enumerate(ca_list):
        if select_list[i]:
            r -= np.array(ca[1:])
            money += ca[0]
    for i in r:
        if i > 0: c = False
    if c:
        ans = min(ans, money)
if ans == 10**7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=10**18
for i in range(2**n):
  flag=format(i,'b')
  flag='0'*(n-len(flag))+flag
  tmp=0
  check=[0]*(m)
  for j in range(n):
    if flag[j]=='0':
      continue
    tmp+=arr[j][0]
    for k in range(m):
      check[k]+=arr[j][k+1]
  for j in range(m):
    if check[j]<x:
      break
  else:
    ans=min(ans,tmp)
if ans==10**18:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n, m, x = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l = np.array(l)
ans = np.sum(l, 0)[0]
ans_s = np.sum(l, 0)
if np.any(ans_s[1:] < x):
    print(-1)
    exit()
for i in range(1, n + 1):
    for j in itertools.combinations(l, i):
        tot = np.sum(j, 0)
        if np.all(tot[1:] >= x) and tot[0] < ans:
            ans = tot[0]
print(int(ans))

Submission status: Accepted

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


ans = 10**10

for bit in range(1<<n):
    b = [0]*m
    c =0
    for i in range(n):
        if bit & 1<<i:
            for j in range(m):
                b[j]+=a[i][j+1]
            c += a[i][0]
    if min(b)>=x:
        ans = min(ans,c)

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

Submission status: Accepted

Solution code:
n,m,x=map(int, input().split())
c =[list(map(int, input().split())) for i in range(n)]
ch = [0 for i in range(m+1)]
ans = 10000000000
a,all = [],[]
for i in range(1,n+1):
    a.append(i)
for i in range(1,2**len(a)):
    b = []
    for j in range(len(a)):
        if (i >> j) &1 == 1:
            b.append(a[j])
    all.append(b)
for i in range(len(all)):
    ch = [0 for i in range(m+1)]
    for j in range(len(all[i])):
        k = all[i][j]-1
        ch = [x+y for (x,y) in zip(ch,c[k])]
    t = 0
    for j in range(1,m+1):
        if ch[j] < x:
            t = 1
    if t == 0 and ans > ch[0]:
        ans = ch[0]
if ans == 10000000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

if __name__ == '__main__':
    T = input().split()
    N = int(T[0])
    M = int(T[1])
    X = int(T[2])
    price = np.zeros(N)
    qual = np.zeros((N, M))
    for n in range(N):
        t = input().split()
        price[n] = int(t[0])
        qual[n, :] = np.array([int(m) for m in t[1:]])

    cost_min = 1e18
    for idx in product([0, 1], repeat=N):
        cost = 0
        t = X * np.ones(M)
        for j in range(N):
            if idx[j] == 1:
                t -= qual[j, :]
                cost += price[j]
        if max(t) <= 0:
            if cost < cost_min:
                cost_min = cost
    if cost_min == 1e18:
        print(-1)
    else:
        print(int(cost_min))

Submission status: Accepted

Solution code:
def main():
    N, M, X = map(int, input().split())

    A = [[] for _ in range(N)]
    C = [0] * N

    INF = 10 ** 9
    ans = INF

    for i in range(N):
        c_as = list(map(int, input().split()))
        C[i], A[i] = c_as[0], c_as[1:]

    for s in range(0, 1 << N):
        smart = [0] * M
        cost_sum = 0
        for i in range(N):
            if (s >> i) % 2 == 0:
                continue
            cost_sum += C[i]
            for j in range(M):
                smart[j] += A[i][j]

        ok = True
        if min(smart) < X:
            ok = False

        if ok:
            ans = min(ans, cost_sum)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
n,m,x = map(int,input().split())
l = [[0]*(m+1) for i in range(n)] #入力の通りに2次元リストに入れる
for i in range(n):
    k = list(map(int,input().split()))
    for j in range(m+1):
        l[i][j] = k[j]
seq = [i for i in range(n)] #0~n-1のリストを作る
combis = [] #選ぶ参考書の組み合わせたちのリスト
for i in range(1,n+1): #i個選ぶ時の組み合わせを上で作ったリストに加えていく
    combis += list(combinations(seq,i))
ans = [] #条件を満たした組み合わせの合計金額たちを入れるリスト
for p in combis: #全ての組み合わせを試していく
    pcomp = [0]*m #組み合わせpの時の理解度
    pmoney = 0 #組み合わせpの時の金額
    for q in p: #組み合わせpの時に買う参考書q
        for j in range(m):
            pcomp[j] += l[q][j+1] #理解度のリストpcompに得られた理解度を足していく
        pmoney += l[q][0] #参考書qを買った時に値段を追加
    flag = True #目標達成したかどうか
    for i in pcomp:
        if i < x:
            flag = False
            break
    if flag: #目標達成したならこの組み合わせの合計金額をメモ
        ans.append(pmoney)
if ans == []: #満たした組み合わせがないなら
    print(-1)
else: #満たした組み合わせがあるなら金額の最小値を出力
    print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np
# N, M, X = map(int, input().split())
#
# A = []
# C = []
#
# for i in range(N):
#     L = list(map(int, input().split()))
#     C.append(L[0])
#     A.append(L[1:])
#
# CC = np.array(C)
# AA = np.array(A)
#
# if np.min(np.sum(AA, axis=0)) < X:
#     print('-1')
# else:
#   ans=np.sum(CC)
#
#   import itertools
#   origin_list = list(range(N))
#   for i, _ in enumerate(origin_list, 1):
#       for j in itertools.permutations(origin_list, r=i):
#           SA = np.zeros(M)
#           COST = 0
#           for id in j:
#               SA += AA[id]
#               COST += CC[id]
#           if np.min(SA)>=X and ans > COST:
#               ans = COST
#   print(ans)

n, m, x = map(int, input().split())
c = []
a = []

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

INF = 1001001001
ans = INF

# n = ビット数とみなしてfor文を回す
for s in range(0,1<<n): # 2のn乗.
    cost = 0
    d = [0]*m
    for i in range(n): #
        if s>>i&1: # sのiビット目が1かどうか判定する
            cost += c[i]
            for j in range(m):
                d[j] += a[i][j]
    ok = True
    for j in range(m):
        if d[j] < x:
            ok = False
    if ok:
        ans = min(ans, cost)

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

Submission status: Accepted

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

ans = 10**7
for i in range(1, 2**n):
    temp = [0] * (m+1)
    for j in range(n):
        if (i >> j) & 1:
            for k, v in enumerate(c[j]):
                temp[k] += v
    if min(temp[1:]) >= x:
        ans = min(temp[0], ans)

print(ans if ans != 10**7 else -1)

Submission status: Accepted

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

ans   = 10**30
cost  = 0
score = [0]*m

for i in range(1<<(n+1)):
  for j in range(n):
    # if (j>>i)&1:
    if i&(1<<j):
      for k in range(m):
        score[k] += li[j][k+1]
      cost += li[j][0]
  if min(score)>=x:
    ans = min(ans,cost)
  score = [0]*m
  cost = 0

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

Submission status: Accepted

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

Min_price = 12*(10**5)
Check = 0                   ####条件を満たす場合があるかどうか

for i in range(2**N):
  binary = str(format(i,'b'))
  binary_zero = binary.zfill(N)
  price = 0
  skill = [0]*M
 
  for j in range(N):         ####binary_zeroについて（bit探索）
    if binary_zero[j]=='1':
      price += L[j][0]
      for k in range(M):
        skill[k] += L[j][k+1]

  if min(skill)>=X:      
    Min_price = min(Min_price,price)
    Check = 1                ####スキルについて条件を満たしたので1
    
if Check==0:
  print(-1)
else:
  print(Min_price)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(n)]
inf = float("inf")
ans = 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 != inf else -1)

Submission status: Accepted

Solution code:
import numpy as np

def main():
    n, m, x = map(int, input().split())
    c = [None]*n
    a = [None]*n
    for i in range(n):
        ca = list(map(int, input().split()))
        c[i] = ca[0]
        a[i] = ca[1:]

    ms = -1

    for i in range(2**n):
        mm = np.zeros([m])
        p = 0
        for j in range(n):
            if i>>j & 1:
                mm += a[j]
                p += c[j]
        if all(mm >= x) and (ms < 0 or ms > p):
            ms = p

    print(ms)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Q = []
B = [0] * N
C = [0] * (M + 1)
flag = True
MIN = -1
for i in range(N):
  Q.append(list(map(int, input().split())))
  
for i in range(2 ** N):
  C = [0] * (M + 1)
  flag = True
  for j in range(N):
    B[j] = (i >> j) & 1
    
  for j in range(N):
    if B[j] == 1:
      for k in range(M + 1):
        C[k] += Q[j][k]
  for j in range(1, M + 1):
    if C[j] < X:
      flag = False
  if flag == True and (MIN == -1 or MIN > C[0]):
    MIN = C[0]
print(MIN)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = []
M = []

for _ in range(n):
    c, *mi = map(int, input().split())
    C.append(c)
    M.append(mi)

res = 10**10

for i in range(1 << n):
    tmp = 0
    cnt = [0] * m
    for j in range(n):
        if (i >> j) & 1 == 1:
            tmp += C[j]
            for k in range(m):
                cnt[k] += M[j][k]
    if min(cnt) >= x:
        res = min(res, tmp)

if res == 10**10:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
from itertools import combinations
n,m,x = map(int,input().split())
l = [[0]*(m+1) for i in range(n)]
for i in range(n):
    k = list(map(int,input().split()))
    for j in range(m+1):
        l[i][j] = k[j]
seq = [i for i in range(n)] #0~n-1のリストを作る
combis = [] #選ぶ参考書の組み合わせたちのリスト
for i in range(1,n+1): #i個選ぶ時の組み合わせを上で作ったリストに加えていく
    combis += list(combinations(seq,i))
ans = [] #条件を満たした組み合わせの合計金額たちを入れるリスト
for p in combis: #全ての組み合わせを試していく
    pcomp = [0]*m #組み合わせpの時の理解度
    pmoney = 0 #組み合わせpの時の金額
    for q in p: #組み合わせpの時に買う参考書q
        for j in range(m):
            pcomp[j] += l[q][j+1] #理解度のリストpcompに得られた理解度を足していく
        pmoney += l[q][0] #参考書qを買った時に値段を追加
    flag = True #目標達成したかどうか
    for i in pcomp:
        if i < x:
            flag = False
            break
    if flag: #目標達成したならこの組み合わせの合計金額をメモ
        ans.append(pmoney)
if ans == []: #満たした組み合わせがないなら
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
from operator import add
N,M,X = map(int, input().split())
tmp = [list(map(int,list(input().split()))) for i in range(N)]
c= []
a = [[] for i in range(N)]
result = []
for i in range(N):
    c.append(tmp[i][0])
    a[i].extend(tmp[i][1:])

for bit in range(1 << (N)):
    suma = [0] * M
    disc = [X] * M
    c4i = []
    rsum = 0
    for i in range(N):
        if (bit & (1<<i)):
            # ここでとった要素を一個づつ見る
            suma = map(add,suma,a[i])
            c4i.append(i)
    suma = list(suma)
    # print(c4i)
    # print(suma,disc)
    # print(suma>=disc)
    flag = True
    for v in range(M):
        if suma[v] < disc[v]:
            flag = False
    if flag:
        for t in c4i:
            rsum = rsum + c[t]
        result.append(rsum)
# print(result)
if result:
    print(min(result))
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X = map(int, input().split())
C = []
A = []
for _ in range(N):
    Cs,*As = map(int,input().split())
    C.append(Cs)
    A.append(As)
INF = float('inf')
ans = INF
for S in range(1<<N):
    B = [0]*M
    cst = 0
    for i in range(N):
        if (S>>i)&1:
            cst+= C[i]
            for j in range(M):
                B[j] += A[i][j]
        if min(B)>=X:
            ans = min(ans,cst)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,y = map(int, input().split())
l = [input().split() for x in range(n)]
c = [0]*n
a=[[0 for x in range(m)] for y in range(n)]
for i in range(n):
    c[i] = l[i][0]
    for j in range(m):
        a[i][j] = l[i][j+1]

ans=float('inf')
for i in range(2 ** n):
    cost = 0
    d=[0]*m
    for j in range(n):
        if i >> j & 1:
            cost += int(c[j])
            for k in range(m):
                d[k] += int(a[j][k])
    ok = True
    for x in range(m):
        if d[x] < y: ok = False
    if ok: 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 = []
L = []
for i in range(N):
    B = list(map(int, input().split()))
    C.append(B[0])
    L.append(B[1:])

res = 10 ** 9
for i in range(2 ** N):
    c = 0
    s = [0 for _ in range(M)]
    for j in range(N):
        if i >> j & 1:
            c += C[j]
            for k in range(M):
                s[k] += L[j][k]
    for j in range(M):
        if s[j] < X:
            break
    else:
        res = min(res, c)

if res == 10 ** 9:
    print(-1)
else:
    print(res)

Submission status: Accepted

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

for i in range(n):
    i = list(map(int,input().split()))
    l.append(i)

ans = []

for j in range(2**n):
    total = 0
    tmp = [0]*m
    for k in range(n):
        if ((j >> k) & 1):
            total += l[k][0]
            for o in range(1,m+1):
                tmp[o-1] += l[k][o]
    if all(t >= x for t in tmp):
        ans.append(total)

if ans:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ar=[list(map(int,input().split())) for i in range(n)]
cost=1e9
p=pow(2,n)
for i in range(p):
    temp=[0 for y in range(m+1)]
    pt=bin(i)[2:].zfill(n)
    for j in range(n):
        if pt[j]=='1':
            for k in range(m+1):
                temp[k]+=ar[j][k]
    z=1
    for j in range(1,m+1):
        if temp[j]<x: z=0
    if z: cost=min(temp[0],cost)
if cost==1e9: print(-1)
else: print(cost)

Submission status: Accepted

Solution code:
import itertools

nums = [int(e) for e in input().split()]

list0 = []
A = []
A0 = list(range(0,nums[0]))
for i in range(0, nums[0]):
    val = [int(e) for e in input().split()]
    list0.append(val)
    for x in itertools.combinations(A0,i+1):
        A.append(list(x))

Z = [0]
for i in range(1,nums[1]+1):
    Z.append(nums[2])

X = []
for i in range(0,len(A)):
    Y = [0] * (nums[1]+1)
    for j in range(0,len(A[i])):
        Y = [x + y for (x, y) in zip(Y,list0[A[i][j]])]
    W = [x - y for (x, y) in zip(Y,Z)]
    if min(W) >= 0:
        X.append(Y[0])

if len(X) > 0:
    print(min(X))
else:
    print('-1')

Submission status: Accepted

Solution code:
import numpy as np

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

values = []
scores = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    values.append(tmp[0])
    scores.append(tmp[1:])
scores = np.array(scores)
values = np.array(values)

def df(arg, score, tmp,args):
    tmps = []
    if arg==N:
        if len(np.where(score>=X)[0]) == M:
            return tmp
        else:
            return 0
    check = df(arg+1, score, tmp, args)
    if check:
        if type(check)==list:
            tmps.extend(check)
        else:
            tmps.append(check)
    check = df(arg+1, score+scores[arg], tmp+values[arg], args+[arg])
    if check:
        if type(check)==list:
            tmps.extend(check)
        else:
            tmps.append(check)
    if tmps == []:
        return 0
    else:
        return tmps

tmp = df(0, np.zeros(M), 0, [])
if tmp != 0:
    print(min(tmp))
else:
    print(-1)

Submission status: Accepted

Solution code:
import copy
N,M,X=map(int,input().split())
A=[0]*(N)
for i in range(N):
  A[i]=[int(x) for x in input().split()]
def nap(p,q):
  if q==N:
    if min(p[1:M+1])>=X:
      lity[-1]=min(lity[-1],p[0])
    return
  nap(copy.copy(p),q+1)
  for i in range(M+1):
    p[i]=p[i]+A[q][i]
  nap(copy.copy(p),q+1)
lity=[]
lity.append(10**9)
r=[0]*(M+1)
nap(r,0)
if lity[-1]==10**9:
  print(-1)
else:
  print(lity[-1])

Submission status: Accepted

Solution code:
a,b,c=map(int,input().split())
d=[list(map(int, input().split())) for i in range(a)]
ans=10**9+7
t2=0
for i in range(2**a):
  e=[0 for j in range(b)]
  f=[0 for j in range(a)]
  ex=0
  for j in range(a):
    if (i//(2**j))%2==1:
      ex+=d[j][0]
      for k in range(b):
        e[k]+=d[j][k+1]
  t1=1
  for j in range(b):
    if c>e[j]:
      t1=0
      break
  if t1 and ans>ex:
    ans=ex
    t2=1
if t2:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M,X=map(int, input().split())
book = []
for _ in range(N):
    book.append(list(map(int, input().split())))
book = np.array(book)
money=pow(10,7)
for i in itertools.product([0,1], repeat=N):
    book2=book
    dellist = []
    for n,l in enumerate(i):
        if l==0:
            dellist.append(n)
    book2=np.delete(book2, dellist, 0)
    ansar = np.sum(book2,axis=0)
    if np.sum(ansar[1:]>=X)==M:
        if money>ansar[0]:
            money = ansar[0]
if money == pow(10,7):
    print(-1)
else:
    print(money)

Submission status: Accepted

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

ans = float('inf')
for i in range(1 << N):
    smart = [0 for _ in range(M)]
    cost = 0
    for j in range(N):
        if (i >> j) & 1:
            cost += C[j]
            for k in range(M):
                smart[k] += A[j][k]
    ok = True
    for j in range(M):
        if smart[j] < X:
            ok = False
    if ok:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
from itertools import product
n,m,x = [int(x) for x in input().split()]
c = []
a = []
for _ in range(n):
    tmp = [int(x) for x in input().split()]
    c.append(tmp[0])
    a.append(tmp[1:])

ans = 1<<60

for v in product([0,1], repeat=n):
    score = [0]*m
    money = 0
    for j in range(n):
        if v[j] == 1:
            money += c[j]
            for k in range(m):
                score[k] += a[j][k]
    if min(score) >= x:
        ans = min(ans,money)

if ans == 1<<60:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
S=[0]*M
C=[]
ans=0

for i in range(N):
    A=list(map(int,input().split()))
    C.append(A)
    ans+=A[0]
    for j in range(M):
        S[j]+=A[j+1]

if min(S)<X:
    print(-1)
    exit()

for b in range(2**N):
    p=0
    S=[0]*M
    for i in range(N):
        if ( b >> i )&1:
            for j in range(M):
                S[j]+=C[i][j+1]
            p+=C[i][0]
    if min(S)>=X and p<ans:
        ans=p

print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
li1 = []
li2 = []
for i in range(n):
    li1.append(list(map(int,input().split())))
for i in range(2**n):
    b = '0'*(n-len(bin(i))+2)+bin(i)[2:]
    total = 0
    li3 = [0]*m
    f = 1
    for j in range(n):
        if b[j] == "1":
            total += li1[j][0]
            for k in range(m):
                li3[k] += li1[j][k+1]
    for j in range(m):
        if li3[j] < x:
            f = 0
    if f == 1:
        li2.append(total)
if len(li2) >= 1:
    print(min(li2))
else:
    print(-1)

Submission status: Accepted

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

ans = 1000000000
for k in range(1, 2**N):
  price = 0
  rikaido=[0]*M
  for l in range(N):
    if k>>l & 1:
      #if CAAA[m][1] < price:
      price += int(CAAA[l][0])
      for t in range(M):
        rikaido[t] += int(CAAA[l][t+1])
        for r in rikaido:
          if r < X:
            break
        else:
          ans = min(ans, price)
if ans == 1000000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

ans = 1e18

for i in range(1 << n):
    skills = [0] * m
    cost = 0
    for j in range(n):
        if i & (1 << j):
            cost += books[j][0]
            for k in range(m):
                skills[k] += books[j][k + 1]
    for j in range(m):
        if skills[j] < x:
            cost = 1e18
    ans = min(ans, cost)

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

Submission status: Accepted

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

A = [0]*M #[0, 0, 0, …]を生成
for ca in CA: #CAの行を抽出
    for i in range(1,M+1): #CAの行の中の要素を抽出
        a = ca[i]
        A[i-1]+=a #それぞれの理解度の合計を計算

if min(A) < X:
    print(-1)
else:
    K = 2**N #2のN乘
    ans = inf #無限大を定義
    for i in range(K):
        b = bin(i) #iを2進数に変換(型は文字列)
        b = b.lstrip("0b") #bから'0b'を除去
        while (len(b)) < N:
            b = "0"+b

        A = [0]*M
        cost = 0
        for j in range(N):
            if b[j] == "1":
                ca = CA[j]
                for k in range(M+1):
                    if k == 0:
                        cost+=ca[k] #合憲金額を計算
                    else:
                        A[k-1] += ca[k]

        if min(A) >= X:
            ans = min(ans,cost)

    print(ans)

Submission status: Accepted

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,x=n1()
ca=n3(n)
ans=9999999999

import itertools
book=list(itertools.product([0,1], repeat=n))
price=[]
for line in book:
    p=0
    for i in range(n):
        if line[i]==1:
            p+=ca[i][0]
            
    price.append(p)
for i in range(len(book)):
    t=book[i]
    s=[0]*m
    for j in range(n):
        if t[j]==1:
            s=[s[k]+ca[j][k+1] for k in range(m)]
    if len([y for y in s if y>=x])==m:
        ans=min(ans,price[i])
if ans==9999999999:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

def main():
    n,m,x=map(int,input().split())
    C=[]
    As=[]
    for _ in range(n):
        c,*A=map(int,input().split())
        C.append(c)
        As.append(A)
    ans=float('inf')
    for i in range(1<<n):
        S=[0]*m
        tmp=0
        for j,(c,A) in enumerate(zip(C,As)):
            if (i>>j)&1==0:
                continue
            tmp+=c
            for k,a in enumerate(A):
                S[k]+=a
        if min(S)>=x:
            ans=min(ans,tmp)
    print(-1 if ans==float('inf') else ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:

import itertools
import sys
import numpy as np
INF = float("inf")
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:
import itertools
n, m, x = map(int, input().split())
T = [list(map(int, input().split())) for _ in range(n)]

flag1 = True
ans = -1

for i in range(1, n + 1):
    if i == 1:
        for j in range(n):
            flag = True
            for k in range(m):
                if T[j][k + 1] < x:
                    flag = False
                    break

            if flag == True and flag1 == True:
                ans = T[j][0]
                flag1 = False
            elif flag == True:
                ans = min(ans, T[j][0])

    else:
        tmp = list(itertools.combinations(range(1, n + 1), i))
        for j in range(len(tmp)):
            flag = True
            M = [0] * m
            tmp1 = 0
            for k in range(len(tmp[j])):
                for l in range(m):
                    M[l] = M[l] + T[tmp[j][k] - 1][l + 1]
                tmp1 = tmp1 + T[tmp[j][k] - 1][0]

            for k in range(m):
                if M[k] < x:
                    flag = False
                    break

            if flag == True and flag1 == True:
                ans = tmp1
                flag1 = False
            elif flag == True:
                ans = min(ans, tmp1)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,x=list(map(int,input().split()))
ans=10**18
A=[list(map(int,input().split())) for i in range(n)]
for i, _ in enumerate(A,1):
  for j in itertools.combinations(A,r=i):
    B=list(zip(*j))    
    C=[sum(B[m]) for m in range(m+1)]
    if len([i for i in C[1:] if i>=x ])==m:
      ans=min(ans,C[0])
print(ans) if ans!=10**18 else print(-1)