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 itertools
n,m,x=map(int,input().split())
l=[[0]]*n
ln=[0]*m
kan=0
for i in range(n):
  l[i]=list(map(int,input().split()))
  for j in range(m+1):
    if j==0:
      kan+=l[i][j]
    else:
      ln[j-1]+=l[i][j]
if sorted(ln)[0]<x:
  print(-1)
else:
  mkan=-1
  for i in range(n+1):
    itr=itertools.combinations(range(n),i)
    for comb in itr:
      kan=0
      ln=[0]*m
      for j in comb:
        kan+=l[int(j)][0]
        for ii in range(m):
          ln[ii]+=l[int(j)][ii+1]
      if sorted(ln)[0]>=x:
        if mkan==-1 or mkan>kan:
          mkan=kan
  print(mkan)

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
from itertools import accumulate, permutations, combinations, product
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
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()
L = [LIST() for i in range(N)]

dp =[[0] * (1+M) for i in range(1+N)]

A = []
B = [0] * M
C = []
for l in L:
    c = l[0]
    C.append(c)
    A.append(l[1:])
    for i, a in enumerate(l[1:]):
        B[i] += a
# print(B)

for b in B:
    if b < X:
        print(-1)
        exit()

L = [0, 1] #生成する数字
num = N #生成するビット数
bit_list = list(product([0, 1], repeat=N))
# print(bit_list)
ma = INF
for bit in bit_list:
    bit = list(bit)
    # print(bit)
    # print(bit)
    l = [0] * M
    cost = 0
    for i, b in enumerate(bit):
        if b == 1:
            for m, a in enumerate(A[i]):
                l[m] += a
            cost += C[i]
    # print(l, cost)
    # print(l)
    cnt = 0
    for k, b in enumerate(l):
        if b >= X:
            cnt += 1
    if cnt == M:
        # print(l)
        # print(cost)
        ma = min(ma, cost)
print(ma)








# for i in range(1, N+1):
#     for j in range(1, M+1):
#         c = C[i]
#         if i - w

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
ans=-1
C=[]; A=[]
flag=[[]]*(1<<N)

#bitマスク生成
for i in range(1<<N):
    d=[0]*N
    for j in range(N):
        if (i>>j)&1==1: d[j]=1
    flag[i]=d
#入力
for i in range(N):
    inp=list(map(int,input().split()))
    C.append(inp[0]); A.append(inp[1:])
#処理
for i in range(1<<N):
    f=flag[i]
    exp=[0]*M; yen=0
    for j in range(N):
        a=A[j]
        if f[j]==1:
            for k in range(M): exp[k]+=a[k]
            yen+=C[j]
    ok=True
    for j in range(M):
        if exp[j] < X: ok=False
    if ok: ans=min(ans,yen) if ans!=-1 else yen
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
N, M, X = map(int, input().split())
T = []
cost = 0
is_update = False
for _ in range(N):
    t = list(map(int, input().split()))
    cost += t[0]
    T.append(t)

for i in range(1, N+1):
    for c in combinations(T, i):
        c = np.array(c)
        _cost = c[:, 0].sum()
        if (c[:, 1:].sum(axis=0) >= X).all() and _cost <= cost:
            cost = _cost
            is_update = True
print(cost if is_update else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import itertools as it


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

    book = []

    for n in range(N):
        book.append(list(map(int, input().split())))
    
    ok = False

    mini = 10**15
    for n in range(1, N+1):
        for v in it.combinations([x for x in range(1, N+1)], n):

            us = [0]*(M+1)
            flag = True
            for i in list(v):
                for j in range(1, M+1):
                    us[j] += book[i-1][j]
            for i in us[1:]:
                if i < X:
                    flag = False
                    break

            if flag:
                ok = True
                temp = 0
                for i in v:
                    temp += book[i-1][0]
                if mini > temp:
                    mini = temp
    
    if ok:
        print(mini)
    else:
        print(-1)
                    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N, M, X = (int(i) for i in input().split())
Y = np.zeros((N, M+1))
for i in range(N):
    Y[i,:] = [int(i) for i in input().split()]
C = Y[:,0]
A = np.matrix(Y[:,1:])
res = np.inf
f = '0'+str(N)+'b'
for i in range(2**N):
    z = np.array([int(s) for s in list(format(i, f))])
    cost = z @ C
    skill = z * A
    if (skill >= X).all() and (cost < res):
        res = cost
if np.isinf(res):
    print(-1)
else:
    print(int(res))

Submission status: Accepted

Solution code:
import itertools
N,M,X = map(int, input().split())
S = []
N_list = list(range(1,N+1))
for _ in range(N):
    c = list(map(int, input().split()))
    S.append(c)
min = 1200001
for i in range(1,N+1):
    c = list(itertools.combinations(N_list, i))
    for v in c:
        A = [0]*M
        money = 0
        flag =0
        for i in range(len(v)):
            book = v[i]
            book_list = S[book-1]
            money += book_list[0]
            for t in range(M):
                A[t] += book_list[t+1]
        for s in A:
            if s<X:
                flag = 1
                break
        if flag == 0:
            if money <= min:
                min = money

if min == 1200001:
    print(-1)
else:
    print(min)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M,X = (int(x) for x in input().split())
S = []
C = []
l = []
ans = 10000000
for i in range(N):
  l.append(i)
for i in range(N):
  s = [int(x) for x in input().split()]
  S.append(s)
npS = np.array(S)
#print(npS)
for i in range(1,N+1):
  if i == 1:
    continue
  C =  list(itertools.combinations(l,i)) + C
#print(C)
for i in C:
  wa = np.zeros(M+1)
  #print("#",wa,S)
  for j in range(len(i)):
   # print(j,wa)
    wa = wa + S[i[j]]
  #print(i,wa)
  cnt = 0
 # print(len(wa))
  for k in range(0,len(wa)):
    if k == 0:
      continue
    if wa[k] >= X:
      cnt += 1
   # print(cnt,(ans > wa[0]))
    if cnt == M and ans > wa[0]:
      ans = wa[0]
for i in range(N):
  cnt = 0
  for j in range(M+1):
    if j == 0:
      continue
    if S[i][j] >= X:
      cnt += 1
    if cnt == M and ans > S[i][0]:
      ans = S[i][0]
if ans == 10000000:
  print(-1)
else:
  print(int(ans))

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]
cnt = [i for i in range(n)]
ans = 10**12
ok = False
for i in range(1,n+1):
    for conb in itertools.combinations(cnt, i):
        z = [0]*(m+1)
        for j in conb:
            for k in range(m+1):
                z[k] = z[k] + ca[j][k]
            if sum(l >= x for l in z[1:]) == m:
                ans = min(ans, z[0])
                ok = True
if ok:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools

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

minnum = (10**5) * 13

for i in range(1, n + 1):
    tmp = list(itertools.combinations(c, i))
    # print(tmp)
    for item in tmp:
        t = list(zip(*item))
        xs = [sum(t[j]) if sum(t[j]) >= x else False for j in range(1, m + 1)]
        if False not in xs and sum(t[0]) < minnum:
            minnum = sum(t[0])
if minnum != (10**5) * 13:
    print(minnum)
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations
N, M, X = map(int, input().split())
C = []
A = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    C.append(tmp[0])
    A.append(tmp[1:])
del tmp
costs = []
for i in range(1, N + 1):
    comb_idx = combinations(range(N), i)
    for indices in comb_idx:
        sub_A = [A[idx] for idx in indices]
        sub_C = [C[idx] for idx in indices]
        sum_sub = [0] * M
        for row in sub_A:
            for j, v in enumerate(row):
                sum_sub[j] += v
        if all(X <= v for v in sum_sub):
            costs.append(sum(sub_C))
if costs:
    print(min(costs))
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

n, m, x= map(int, input().split())
a = [input().split() for l in range(n)]
npa=np.array(a, dtype=int)

hon=-1
for i in range(1,n+1):
  base = list(itertools.combinations(range(0,n),i))
#  print (base)
  
  for j in base:
    totalv=np.sum(npa[j,], axis=0)
#    print (totalv, min(totalv[1:-1]))
    
    if (min(totalv[1:m+1]) >= x):
      if (hon == -1): hon=totalv[0]
      if (hon >= totalv[0]): hon=totalv[0]
#      print (hon)
      
print (hon)

Submission status: Accepted

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

C=[0] * N
A=[0] * N

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

n=0
s=100000000

for i in range(2**N):
  score=[0]*M
  s_tmp=0
  for j in range(N):
    if ((1 << j) & i) >> j == 1:
      s_tmp+=C[j]
      for k in range(M):
        score[k]+=A[j][k]
  flg=1
  for k in range(M):
    if score[k] < X:
      flg=0
      break
  if flg==1:
    if s_tmp < s:
      s=s_tmp
if s == 100000000:
  print(-1)
else:
  print(s)

Submission status: Accepted

Solution code:
from itertools import chain, combinations


def powerset(iterable):
    s = list(iterable)
    sets = list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))
    sets = [s for s in sets if len(s) > 0]
    return sets

def check_row(row, x):
    for el in row:
        if el < x:
            return False
    return True

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

result = float("inf")
sets = powerset([i for i in range(n)])

for s in sets:
    k_rows = [0 for i in range(m)]

    cost = 0
    for idx in s:
        cur_c_k = c_k_table[idx]
        cost += cur_c_k[0]

        k_row = list(cur_c_k[1:])
        for i in range(m):
            k_rows[i] += k_row[i]
    
    if check_row(k_rows, x):
        result = min(result, cost)
if result == float("inf"):
    print(-1)
else:
    print(result)

Submission status: Accepted

Solution code:
import bisect
import collections
import heapq
import math
import operator as op
from collections import Counter
from functools import reduce

import numpy as np


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def main():
    N, M, X = get_inputs(int)
    Cs = np.empty(N, dtype=np.int)
    A_mat = np.empty((N, M), dtype=np.int)
    for i in range(N):
        CAs = get_inputs(int)
        Cs[i] = CAs[0]
        for j in range(M):
            A_mat[i, j] = CAs[j+1]
    # print(Cs)
    # print(A_mat)

    # print(np.sum(A_mat, axis=0))
    if (np.sum(A_mat, axis=0) >= X).all():
        def dfs(i, As_cur, C_cur):
            # Buy Ci
            As_buy = As_cur + A_mat[i, :]
            C_buy = C_cur + Cs[i]
            if (As_buy >= X).all():
                # Accomplish
                # return C_buy
                pass
            else:
                if i < N-1:
                    C_buy = dfs(i+1, As_buy, C_buy)
                else:
                    C_buy = float("inf")

            # Don't buy Ci
            if i < N-1:
                C_dontbuy = dfs(i+1, As_cur, C_cur)
            else:
                C_dontbuy = float("inf")

            return min(C_buy, C_dontbuy)

        ans = dfs(0, np.zeros(M, dtype=np.int), 0)
        assert ans != float("inf")
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

c = [0] * (n)
a = [0] * (n)

ans = 0

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

a_rev = list(zip(*a))
for i in range(len(a_rev)):
  if sum(a_rev[i]) < x:
    print("-1")
    exit()

# print(c)
min_cost = sum(c)

num = len(a)
for i in range(2 ** num):
  bag = []
  bag_skill = []
  for j in range(num):
    if ((i >> j) & 1):
      # print(c[j])
      # print(j)
      bag.append(c[j])
      bag_skill.append(a[j])

  # print(bag)
  bag_skill = list(zip(*bag_skill))
  now = 0
  for k in range(len(bag_skill)):
    if sum(bag_skill[k]) >= x:
      now += 1
      # print("now = ", now)
    if now == len(bag_skill):
      cost = sum(bag)
      if cost < min_cost:
        min_cost = cost
  
print(min_cost)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
cas=[list(map(int,input().split())) for _ in range(n)]
ans=float('inf')
for i in range(1, 2**n):
    v=0
    us=[0]*m
    for b,ca in zip(bin(i)[2:].zfill(n), cas):
        b=int(b)
        if b==0:
            continue
        v+=ca[0]
        for j,a in enumerate(ca[1:]):
            us[j]+=a
    for u in us:
        fg=0
        if u<x:
            fg=1
            break
    if fg==0:
        ans=min(ans,v)
if i==2**n-1 and fg==1:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
A = [[0 for j in range(M+1)]for i in range(N)]
for i in range(N):
    A[i] = list(map(int,input().split()))

S = 10**10

for i in range(2**N):
    B = [0 for m in range(M+1)]
    SS = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(1,M+1):
                B[k] += A[j][k]
            SS += A[j][0]
    flag = True
    for k in range(1,M+1):
        if B[k] < X:
            flag = False
    if flag and SS < S:
        S = SS

if S == 10**10:
    print('-1')
else:
    print(str(S))

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
books=[]
for i in range(n):
    books.append(list(map(int, input().split())))
#print(books)
perms=[]
for i in range(2**n):
    list2 = []
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(1)
        else:
            list2.append(0)
    perms.append(list2)
#print(perms)
oks=[]
for i in perms:
    cost = 0
    xs = [0]*m
    for idx,j in enumerate(i):
        if j==1:
            cost+=books[idx][0]
            for k in range(m):
                xs[k]+=books[idx][k+1]
    if min(xs)>=x:
        oks.append(cost)
#print(oks)
if oks:
    print(min(oks))
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
ca = []
for i in range(n):
    ca.append(list(map(int,input().split())))
ans = -1
for i in range(1, 1<<n):
    tmp_ca = [0] * len(ca[0])
    for j in range(n):
        if (i>>j)&1:
            tmp_ca[0] += ca[j][0]
            for k in range(len(tmp_ca) - 1):
                tmp_ca[k+1] += ca[j][k+1]
    ok_num = 0
    for j in range(len(tmp_ca) - 1):
        if tmp_ca[j+1] >= x:
            ok_num += 1
    if ok_num == m:
        if ans == -1:
            ans = tmp_ca[0]
        else:
            ans = min(ans, tmp_ca[0])
print (ans)

Submission status: Accepted

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

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

# print(A)

ans = float("inf")
for i in range(2 ** n):
    skill = [0] * (m+1)
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m+1):
                skill[k] += A[j][k]


    # print(ans, skill)

    if skill:
        for i in range(1, m+1):
            if x > skill[i]:
                break
        else:
            ans = min(ans, skill[0])

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

Submission status: Accepted

Solution code:
N,M,X = map(int, input().split())
CA_s = [list(map(int, input().split())) for _ in range(N)]
ans = 10**18
pattern = []
for i in range(2 ** (N)):
    tmp = [False] * N
    for j in range(N):
        if i >> j & 1:
            tmp[j] = True
    price = 0
    rikaidos = [0] * M
    for i in range(len(tmp)):
        if(tmp[i] == True):
            for j in range(M+1):
                if j == 0:
                    price += CA_s[i][0]
                else:
                    rikaidos[j-1] += CA_s[i][j]
    if len(list(filter(lambda x:x<X, rikaidos)))==0 and price<ans:
        ans = price
if ans == 10**18:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

n,m,x = [int(i) for i in input().split()]
data = [input() for _ in range(n)]
data = [[int(i) for i in d.split()] for d in data]

min_total = -1
for m_comb in range(1, n+1):
    for comb in combinations(data, m_comb):
        c_totals = [sum([c[i] for c in comb]) >= x for i in range(1, m+1)]
        if all(c_totals):
            if min_total == -1:
                min_total = sum([c[0] for c in comb])
            if sum([c[0] for c in comb]) < min_total:
                min_total = sum([c[0] for c in comb])
print(min_total)

Submission status: Accepted

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, X = read_ints()
    A = []
    for _ in range(N):
        A.append(read_ints())

    min_T = math.inf
    for S in range(1, (1<<N)):
        T = [0]*(M+1)
        for i in range(0, N):
            if (S>>i)&1 == 1:
                for j in range(M+1):
                    T[j] += A[i][j]
        if all(t >= X for t in T[1:]) and T[0] < min_T:
            min_T = T[0]
    if min_T == math.inf:
        return -1
    return min_T


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import itertools

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

ans = []
for n in range(N):
    all_list = itertools.combinations(range(N), n+1)
    for c in all_list:
        scores = [0 for _ in range(M)]
        price = 0
        for i in c:
            for j in range(M):
                scores[j] += A[i][j]
            price += C[i]
        clear = True
        for j in range(M):
            if scores[j] < X:
                clear = False
        if clear:
            ans.append(price)

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

Submission status: Accepted

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

import numpy as np

ans = N * (10**5)+1


for n in range(2**N):
  ls = [0] * (M+1)
  bin = format(n,'b').zfill(N)
  for i in range(N):
    ls = np.array(ls) + np.array(C[i])*int(bin[i])

  if min(ls[1:]) >= X:
    if ls[0] < ans:
      ans = ls[0]

      
if ans < N * (10**5)+1:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
r = []
for _ in range(n):
    r.append(list(map(int, input().split())))
r_all = [0 for i in range(m+1)]
for i in range(m+1):
    for j in range(n):
        r_all[i] += r[j][i]
def d(r_sum):
    achieved = True
    for u in r_sum[1:]:
        if u < x:
            achieved = False
    return achieved
if d(r_all) == False:
    print(-1)
else:
    ans = r_all[0]
    for i in range(2**n):
        r_sum = [0 for i in range(m+1)]
        buy = '0' * (n-(len(bin(i))-2))+bin(i)[2:]
        for j in range(n):
            if buy[j] == "1":
                for k in range(m+1):
                    r_sum[k] += r[j][k]
        if d(r_sum) == True and r_sum[0] < ans:
            ans = r_sum[0]
    print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, X = map(int, input().split())
C = []
A = dict()
for i in range(N):
    CA = list(map(int, input().split()))
    C.append(CA[0])
    for j in range(1, M+1):
        if j in A:
            A[j].append(CA[j])
        else:
            A[j] = [CA[j]]

cost = float("inf")

for i in range(1, N+1):
    for pm in itertools.combinations(list(range(1, N+1)), r=i):
        c = 0
        k = dict()
        for p in pm:
            c += C[p-1]

            for m in range(1, M+1):
                if m in k:
                    k[m] += A[m][p - 1]
                else:
                    k[m] = A[m][p - 1]

        if min(k.values()) >= X:
            cost = min(cost, c)


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

Submission status: Accepted

Solution code:
# 2020/05/10
# AtCoder Beginner Contest 167 - C

def search(idx, ra, pr):
    if idx >= n:
        if min(ra) >= x:
            return pr
        else:
            return 10**9
    else:
        # Buy Book[idx]
        w_ra = list()
        for j in range(m):
            w_ra.append(ra[j] + ca[idx][j+1])
        
        a1 = search(idx+1, w_ra, pr+ca[idx][0])
        # Don't Buy Book[idx]
        a2 = search(idx+1, ra, pr)
        
        if a1 == 10**9 and a2 == 10**9:
            return 10**9
        elif a1 == 10**9:
            return a2
        elif a2 == 10**9:
            return a1
        else:
            return min(a1, a2)

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

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

minpr = 10**9

wkl = [0] * m
minpr =search(0, wkl, 0)
if minpr == 10**9:
    minpr = -1

print(minpr)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

N, M, X = map(int, input().split())
C_list = []
ans = []

for _ in range(N):
    C_list.append(list(map(int, input().split())))
    
for i in range(1,N+1):
    for j in itertools.combinations(C_list, i):
        a = np.zeros(M+1)
        for k in j:
            a += np.array(k)
        if np.all(a[1:]>=X):
            ans.append(a[0])
if ans:
    print(int(min(ans)))
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
L = [[0 for i in range(m+1)] for j in range(n)]
for i in range(n):
    L[i] = list(map(int, input().split()))

ans = [[0 for i in range(m+1)] for j in range(2**n)]
b = []
count = 0
for i in range(2 ** n):
    tmp = []
    for j in range(n):  
        if ((i >> j) & 1):
            tmp = L[j]  
            for k in range(m+1):
                ans[i][k] = ans[i][k] + tmp[k]

    check = 1
    for k in range(1,m+1):
        if ans[i][k] < x:
            check = 0
    if check:
        b.append(ans[i])


if len(b) == 0:
    print("-1")
else:
    b.sort()
    print(b[0][0])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

N, M, X = map(int, input().split())
C = []
A = []

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

patterns = []

def dfs(buyable, pattern, idx):
    copy = pattern[:]
    if len(copy) == buyable:
        patterns.append(copy)
    elif idx == N:
        return
    else:
        dfs(buyable, copy, idx+1)
        copy.append(idx)
        dfs(buyable, copy, idx+1)

achived = False
_min = sum(C)
for i in range(1, N+1):
    patterns = []
    dfs(i, [], 0)

    for pattern in patterns:
        total = 0
        tmp = [0 for i in range(M)]
        for j in pattern:
            total += C[j]
            for k in range(M):
                tmp[k] += A[j][k]

        if min(tmp) >= X and _min >= total:
            _min = total
            achived = True

if achived:
    print(_min)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
n,m,x = list(map(int,input().split()))
a = []
f = True
res = []
p = 0

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

for k in range(n):
    for i in itertools.combinations(a,k+1):

        f = True
        for l in range(m):
            if f == True:
                c = 0
                p = 0
                for j in range(k+1):
                    if len(i) == 1:
                        c += i[j][l+1]
                    else:
                        c += i[j][l+1]
                if c < x:
                    f = False
           
        if f == True:
            ressum = 0
            for o in range(k+1):
                ressum += i[o][0]
            res.append(ressum)

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

Submission status: Accepted

Solution code:
from itertools import combinations

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

all_text = [list(map(int,input().split())) for i in range(N)]

array = [i for i in range(N)]
comb = []

for i in range(N):
    r = list(map(list,list(combinations(array,i+1))))
    comb.extend(r)

ans = []

for i in comb:
    check = [0 for i in range(M)]
    answer = [0 for i in range(M+1)]
    for j in i:
        for m in range(len(all_text[j])):
            answer[m] += all_text[j][m]
            if m>=1 and answer[m] >= X:
                check[m-1] = 1
    if sum(check) >= M:
        ans.append(answer[0])

if not ans:
    print(-1)
    exit()

ans.sort()
print(ans[0])

Submission status: Accepted

Solution code:
import itertools

N, M, X = map(int, input().split())
C = []
As = []
for _ in range(N):
    vals = list(map(int, input().split()))
    C.append(vals[0])
    As.append(vals[1:])

ans = 10**10
for num in range(N):
    # num = 2
    comb = list(itertools.combinations(enumerate(C), num + 1))
    for vals in comb:
        # vals = comb[0]
        sum_c = 0
        l = [0 for _ in range(M)]
        for idx, c in vals:
            A = As[idx]
            for j in range(len(A)):
                l[j] += A[j]
            sum_c += c
        if min(l) >= X:
            ans = min(sum_c, ans)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
Inf = 10**10
c = [0]*n
a= []
for i in range(n):
  y =  list(map(int,input().split()))
  c[i] = y.pop(0)
  a += [y]
#print(a)
#print(c)
#quit()

def f(i=0, s=[0]*m, p=0):
  if i == n and min(s) >= x:
    #print(s)
    #print(p)
    return p
  elif i == n and min(s) < x:
    return Inf
  else:
    return min(f(i+1,s,p),f(i+1,[s[j]+a[i][j] for j in range(m)],p+c[i]))
  

ans = f()
if ans == Inf:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
l = []
for i in range(n):
    l.append(np.array(input().split(),dtype=int)) 
import itertools
num = [i for i in range(n)]
min = 1000000000000000000000000
k = 1
while k <n+1:
    a = list(itertools.combinations(num, k))
    for i in range(len(a)):
        total =np.zeros(m+1,dtype=int)
        for j in range(len(a[i])):
            total +=l[a[i][j]]
        if np.sum(np.where(total < x)[0]) <=0:
            if min > total[0]:
                min = total[0]
                
    k +=1
if min == 1000000000000000000000000:
    print(-1)
else:
    print(min)

Submission status: Accepted

Solution code:
import sys;input=lambda:sys.stdin.readline().rstrip();ints=lambda:list(map(int,input().split()))
import numpy as np;from itertools import combinations

def main():
    n,m,x=ints()
    ca,val=[],[]
    for _ in range(n):
        inp=ints()
        ca.append(inp)
        flg=1
        for i in range(1,m+1):
            if inp[i]<x:
                flg = 0
        val.append(inp[0]) if flg==1 else None
    for num in range(2,n+1):
        for v in combinations(ca,num):
            vnp = np.array(v)
            s=vnp.sum(axis=0)
            flg=1
            for i in range(1,m+1):
                if s[i]<x:
                    flg = 0
            val.append(s[0]) if flg==1 else None
    print(-1 if not val else min(val))

if __name__ == '__main__':
    main()