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
N, M, X = map(int,input().split())
l = []
li = np.array([])
for i in range(N):
  l.append(list(map(int,input().split())))

li = np.array(l)

skill_sum = []
for j in range(2**N):
  sum = np.zeros([M+1])
  for k in range(N):
    if ((j >> k) & 1):
        sum += li[k] 
  skill_sum.append(list(sum))      
pricelist = []
for l in range(2**N):
  cnt = 0
  for m in range(M):
    if skill_sum[l][m+1] >= X:
      cnt += 1
  if cnt ==  M:
    pricelist.append(int(skill_sum[l][0]))

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

Submission status: Accepted

Solution code:
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
    for j in range(m):
        if smart[j] < x:
            ok = False
    if ok:
        ans = min(ans, cost_sum)

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
A=[]
C=[]
PriceLev=[[0,1] for i in range(2**N)]
EXP=[[0]*M for i in range(2**N)]
for i in range(N):
    A.append(list(map(int,input().split())))
    C.append(A[i].pop(0))

for pat in range(2**N):
    binstr=format(pat,'0'+str(N)+'b')
    for book in range(N):
        if binstr[book] == '1':
            PriceLev[pat][0] += C[book]
            for sub in range(M):
                EXP[pat][sub] += A[book][sub]

    for sub in range(M):
        if EXP[pat][sub] < X:
            PriceLev[pat][1] *= 0

PriceLev.sort(reverse=True, key=lambda x:(x[1],-x[0]))
if PriceLev[0][1]:
    print(PriceLev[0][0])
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

Cmin = 10**10
N, M, X = map(int, input().split())
L = np.array([[int(j) for j in input().split()] for i in range(N)])
for i in range(N):
  for idx in itertools.combinations(list(range(N)), i+1):
    A = np.zeros(M+1, dtype=int)
    A = A + np.sum(L[list(idx)], axis=0)
    if A[0] < Cmin and (A[1:] >= X).all() == True:
      Cmin = A[0]
if Cmin == 10**10:
  print(-1)
  exit()
print(Cmin)

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 i in range(2**N):
    cost = 0
    rikai = [0 for i in range(M)]
    for j in range(N):
        if i>>j&1:
            cost += A[j][0]
            for k in range(M):
                rikai[k] += A[j][k+1]
    b = True
    for k in range(M):
        if rikai[k] >= X:
            continue
        b = False
    if b:
        ans = min(ans,cost)
print(-1 if ans == 10**10 else ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
n, m, x = [int(x) for x in input().split()]
a = np.stack([np.array(input().split(), dtype=int) for _ in range(n)])
tot = np.sum(a, axis=0)
if min(tot[1:]) < x:
    print(-1)
    exit(0)
cost = tot[0]
whole = np.array(list(product([0,1],repeat=n)), dtype=bool)[1:-1]
for flag in whole:
    sel = a[flag]
    tot = np.sum(a[flag], axis=0)
    if min(tot[1:]) >= x and tot[0] < cost:
        cost = tot[0]
print(cost)

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 i in range(2**N):
    cost = 0
    rikai = [0 for i in range(M)]
    for j in range(N):
        if i>>j&1:
            cost += A[j][0]
            for k in range(M):
                rikai[k] += A[j][k+1]
    if min(rikai) >= X:
        ans = min(ans,cost)
print(-1 if ans == 10**10 else ans)

Submission status: Accepted

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

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

for i in range(N):
    *c_as, = map(int, input().split())
    C[i], As[i] = c_as[0], c_as[1:]
    
INF = 10**9
ans = INF
    
# bit全探索
for s in range(1 << N):
    understandings = [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):
            understandings[j] += As[i][j]
        is_able = True
        for i in range(M):
            if understandings[i] < X:
                is_able = False
        if is_able:
            ans = min(cost_sum, ans)
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
def count_up(idx_list, lv_list):
#  print(idx_list, "の組み合わせのカウントアップ")
  new_lv_list = []
  for j in range(M):
    each_total_lv = 0
    for i in idx_list:
      each_total_lv += lv_list[i][j]
#      print(each_total_lv)
      if(each_total_lv >= X):
#        print(j, "番地の能力は達成")
        break
    if(each_total_lv < X):
#      print(idx_list, "だと未達成。次")
      return -1
  
  price = 0;
  for a in idx_list:
    price += prices[a]
  
#  print("idx_list=", idx_list, "金額は", price)
  
  return price
    
  

from itertools import combinations

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

prices = []
lv_ups = []
max_price = 0

# i = 0から
for i in range(N):
  tmp = tuple(map(int, input().split(' ')))
  max_price += tmp[0]
  prices.append(tmp[0])
  lv_ups.append(tmp[1:len(tmp)])

#print("最大金額=", max_price)

all_read = []
complete = True
for j in range(M):
    each_total_lv = 0
    for i in range(len(lv_ups)):
      each_total_lv += lv_ups[i][j]
    
    if (each_total_lv < X):
      complete = False
    all_read.append(each_total_lv)
    
    
# 判定
if(complete):
  for z in reversed(range(1, N)):
    comb = combinations(range(N), z)
    for e in comb:
      counted_price = count_up(e, lv_ups)
      if(counted_price > 0 and max_price > counted_price):
        max_price = counted_price
  
  print(max_price)
  
else:
  print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations as co
n,m,x=map(int,input().split())
A=[]
ansl=[]

for i in range(n):
    A.append(list(map(int,input().split())))
a0,a,b,c,d,e,f,g,h,i,j,k,l=0,0,0,0,0,0,0,0,0,0,0,0,0
alp=[i,(i,j),(i,j,k),(h,i,j,k),(g,h,i,j,k),(f,g,h,i,j,k),(e,f,g,h,i,j,k),(d,e,f,g,h,i,j,k),(c,d,e,f,g,h,i,j,k),(b,c,d,e,f,g,h,i,j,k),(a,b,c,d,e,f,g,h,i,j,k),(a0,a,b,c,d,e,f,g,h,i,j,k)]
for t in range(n):
    for alp[t] in co(range(n),t+1):
        for l in range(1,m+1):
            if sum([A[al][l] for al in alp[t]])<x:
                break
            if l==m:
                ansl.append(sum([A[al][0] for al in alp[t]]))
    if n==t+1:
        print(min(ansl) if len(ansl)>0 else "-1")
        quit()

Submission status: Accepted

Solution code:
n, m, x = [int(x) for x in input().split()]
c = []
a = []
for i in range(n):
  tmp = [int(x) for x in input().split()]
  c.append(tmp[0])
  a.append(tmp[1:])
#全探索
ans = 10**8 # as INF
for s in range(2**n):
  cost = 0
  d = [0 for j in range(m)]
  for i in range(n):
    is_use = bin(s>>i&1) == bin(1)
    if is_use:
      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 and cost < ans:
    ans = cost
if ans == 10**8:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

Cmin = 10**10
N, M, X = map(int, input().split())
L = np.array([[int(j) for j in input().split()] for i in range(N)])
for i in range(N):
  for idx in itertools.combinations(list(range(N)), i+1):
    A = np.zeros(M+1, dtype=int)
    for j in idx:
      A = A + L[j]
    if A[0] < Cmin and (A[1:] >= X).all() == True:
      Cmin = A[0]
if Cmin == 10**10:
  print(-1)
  exit()
print(Cmin)

Submission status: Accepted

Solution code:
n, m, x = [int(i) for i in input().split()]
as_ = []
for _ in range(n):
    as_.append([int(i) for i in input().split()])
suc = []
for i in range(2**n):
    ms = [0]*m
    c = 0
    for ind, b in enumerate(bin(i)[2:][::-1]):
        if b == '1':
            c += as_[ind][0]
            for i_ in range(m):
                i_ += 1
                ms[i_-1] += as_[ind][i_]
    fl = [1 for m_ in ms if m_ >= x]
    if sum(fl) == m:
        suc.append(c)
if suc:
    print(min(suc))
else:
    print(-1)

Submission status: Accepted

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

List = []

Max = 10 ** 7

for i in range(N):
    List.append(list(map(int, input().split())))

for i in range(2 ** N):
    Sum = [0] * (M+1)
    for j in range(N):
        if (i >> j) & 1:
            for k in range(M+1):
                Sum[k] += List[j][k]
    if Sum[0] <= Max:
        for a in range(1, M+1):
            if Sum[a] < X:
                break
        else:
            Max = Sum[0]

if Max == 10 ** 7:
    print(-1)
else:
    print(Max)

Submission status: Accepted

Solution code:
n,m,x=map(int, input().split())
a = [0] * m
ans = 100000000
c = []
p = []
cost=0

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

for i in range(2 ** n):
    for j in range(n):
        if i >> j & 1:
            cost += c[j][0]
            for k in range(m):
                a[k] = a[k] + c[j][k+1]
    if all((l >= x for l in a)):
        ans = min(ans,cost)
    #print(cost,a,ans)
    cost=0
    a = [0] * m

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

Submission status: Accepted

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

cost = 100000000000000000000000
l = list(range(1,N+1))
for i in range(2**N):
    check = [0]*N
    sub_list = [0]*(M+1)
    for j in range(N):
        if (i >> j) & 1 == 1:
            check[j] = 1
    for k in range(N):
        if check[k] == 1:
            for p in range(M+1):
                sub_list[p] += C[k][p]
    flag = True
    for q in range(M):
        if sub_list[q+1] < X:
            flag = False
    if flag == True:
        cost = min(sub_list[0],cost)

if cost == 100000000000000000000000:
    print(-1)
else:
    print(cost)

Submission status: Accepted

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

cost = []

for i in range(2 ** N):
  one = str(bin(i)).count('1')
  ca_list = [0] * M
  c = 0
  for j in range(N):
    if ((i >> j) & 1):
      c += CA[j][0]
      for k in range(M):
        ca_list[k] += CA[j][k+1]
  if min(ca_list) >= X:
    cost.append(c)

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

Submission status: Accepted

Solution code:
from itertools import product
n, m, x = list(map(int, input().split()))
cl = [0] * n
al = [[]*m for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    cl[i] = tmp[0]
    al[i] = tmp[1:]


def dfs(status, book):
    for i in range(m):
        status[i] += book[i]
    return status


ans = 10**10
for bit in product([0, 1], repeat=n):
    # print(bit)
    status = [0]*m
    money = 0
    for i, b in enumerate(list(bit)):
        if b == 1:
            status = dfs(status, al[i])
            money += cl[i]
    flag = True
    for i in range(m):
        if status[i] >= x:
            continue
        else:
            flag = False
    if flag:
        ans = min(ans, money)
if ans == 10**10:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

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

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

    C.append(l[0])
    A.append(l[1:])


# print('NMX', N, M, X)
# print('C', C)
# print('A', A)


def buy_nth_book(x, n):
    if (x >> n) & 1:
        return True
    return False


ans_C = []
ans_A = []

# bit全探索でans_Cに合計代金, ans_Aに獲得能力を入れる
for i in range(2 ** N):
    ans_C.append(0)
    ans_A.append([0 for m in range(M)])
    for n in range(N):
        if buy_nth_book(i, n):
            ans_C[i] += C[n]

            for m in range(M):
                ans_A[i][m] += A[n][m]

res_C = []
# Xの条件を満たすCをリストに入れる
for c, a in zip(ans_C, ans_A):
    if all([aa >= X for aa in a]):
        res_C.append(c)
# ans_A_idx = [ aa for aa in ans_A if [ a >= X for a in aa]]

if res_C:
    print(min(res_C))
else:
    print('-1')

Submission status: Accepted

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


def dfs(n, v, m):
    global N, M, X
    rst = 10 ** 8
    if n == N:
        if all(x >= X for x in m):
            rst = v
    else:
        nv = v + C[n]
        nm = tuple(m[i] + A[n][i] for i in range(M))
        rst = min(dfs(n + 1, v, m), dfs(n + 1, nv, nm))
    return rst


N, M, X = map(int, input().split())
A = [None] * N
C = [None] * N
for i, s in enumerate(sys.stdin.readlines()):
    C[i], *A[i] = map(int, s.split())

rst = dfs(0, 0, tuple([0] * M))
ans = rst if rst < 10 ** 8 else -1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools
import numpy as np

INF = 10 ** 10

N, M, X  = [int(x) for x in stdin.readline().rstrip().split()]
CA = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]
CA = np.array(CA)

nums = [False, True]
buy_or_not = list(itertools.product(nums, repeat=N))

ans = INF

for bn in buy_or_not:
    tmp = CA.T
    data = np.where(bn, tmp, 0)
    data_sum = data.sum(axis=1)

    if min(data_sum[1:]) >= X:
        ans = min(ans, data_sum[0]) 

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

Submission status: Accepted

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

CAM = list([list(map(int,input().split())) for i in range(N)])
# print(CAM)
minn = 10**18
b = False

for i in range(2 ** N):
  s = 0
  am = []

  for j in range(N):  # このループが一番のポイント
      if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
        am.append(CAM[j])

  j = False
  sss = [0] * (M+1)
  for kk in range(len(am)):
    s += am[kk][0]
    for m in range(0, M):
      sss[m+1] += am[kk][m+1]
  
  if len([i for i in sss[1:] if i >= X] ) == len(sss[1:]):
    b = True
    minn = min(s,minn)
  
  # print(sss)
  # if x >= X and y >= X and z >= X:
  #   minn = min(s,minn)
  #   b = True

print(minn if b == True else -1)

Submission status: Accepted

Solution code:
'''
productでrepeatすればいいよ、
0,1リスト生成
minでとれたね
enumerateは手前がindex,valueの順

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

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

#print(targets)
answer = 10 ** 9
for i in range(0,1 << N):
    result = [0] * (M + 1)
    for j in range(N):
        if (i >> j) % 2 == 1:
            for k in range(M + 1):
                result[k] += C_list[j][k]
        #print(result)
    if min(result[1:]) >= X:
        #print(result)
        answer = min(answer,result[0])
if answer == 10 ** 9:
    print(-1)
else:
    print(answer)

Submission status: Accepted

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

def generate_n_bit(n):
    bins= []
    for i in range(2**n):
        bins.append(list(str(format(i,'b').zfill(n))))
    
    return bins

min_price = 10**9
bins = generate_n_bit(n)
bins = bins[1:]

for bin in bins:
    a = [0 for k in range(m)]
    price = 0
    for i in range(n):
        if bin[i] == '1':
            for j in range(m):
                a[j] += l[i][j+1]
            
            price += l[i][0]
    
   
    
    if min(a) >= x:
        min_price = min(price, min_price)
        

if min_price == 10**9:
    print(-1)
    exit()
    
print(min_price)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
cost = 0
flag = 0
min = 10000000000000

for i in range(1<<n):
  r = [0]*m
  flag = 0
  cost = 0
  for j in range(n):
    if(i>>j&1):
      cost += a[j][0]
      for k in range(m):
        r[k] += a[j][k+1]
  for k in range(m):
    if(r[k] < x):
      flag = 1
      break
  if(flag == 0 and min > cost):
    min = cost
if(min == 10000000000000):
  print(-1)
else:
  print(min)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

###
# main
if(__name__ == '__main__'):
    # input
    n, m, x = map(int, input().split(" "))

    book = []
    c_sum = 0
    sum_li = [0 for _ in range(m)]
    for i in range(n):
        b = list(map(int, input().split(" ")))
        book.append(b)
        c = b[0]
        c_sum += c
        for al in range(m):
            a = b[al+1]
            sum_li[al] += a

    ans = -1
    for al in range(m):
        if sum_li[al] < x:
            break
    else:
        q = []
        cost_list = [c_sum]
        init_list = [c_sum]
        for al in range(m):
            init_list.append(sum_li[al])
        q.append(init_list)

        for i in range(n):
            for tgt_cnt in range(len(q)):
                tgt = q[tgt_cnt]
                cost = tgt[0] - book[i][0]
                tgt_list = [cost]
                for al in range(m):
                    cp = tgt[al+1] - book[i][al+1]
                    if cp < x:
                        break
                    else:
                        tgt_list.append(cp)
                else:
                    cost_list.append(cost)
                    q.append(tgt_list)

        cost_list.sort()
        ans = cost_list[0]

    print(ans)

# else:
    # do nothing

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
I = [list(map(int,input().split())) for x in range(N)]
I2 = [I[y].pop(0) for y in range(N)]
total = np.array([0]*len(I[0]))
ans = []
def check(n,total,cost):
    if n > N-1:
        if min(total) >= X:
            ans.append(cost)
            return
        return
    else:
        array = np.array(I[n])
        check(n+1, total + array, cost + I2[n])
        check(n+1, total, cost)
check(0, total, 0)
if not ans:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
import sys
n,m,x= map(int, sys.stdin.readline().rstrip("\n").split())
lines = [ [int(s) for s in line.split()] for line in sys.stdin ]
price = -1
skill = {}
for i in range(2**n-1):
    i = format(i+1, 'b').zfill(n)
    price_ = 0
    for j in range (m):
        skill[j] = 0
    for k in range(n):
        if i[k] == '1':
            price_  += lines[k][0]
            for j in range(m):
                skill[j] = skill[j] + lines[k][j+1]
    for j in range(m):
        if skill[j] < x:
            break
    else:
        if price == -1:
            price = price_
        else:
            price = min(price, price_)
print(price)

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int, input().split())
lst = np.array([np.array(list(map(int, input().split()))) for _ in range(n)])
ans = float('inf')
for i in range(1<<n):
    eff = np.array([0] * (m+1))
    for j in range(n):
        if i>>j&1==1:
            eff += lst[j]
    cost = eff[0]
    eff = eff[1:]
    if np.all(eff >= x):
        ans = min(ans, cost)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as co
n,m,x=map(int,input().split())
A=[]
ansl=[]
for i in range(n):
    A.append(list(map(int,input().split())))
for i in range(n):
    for j in range(1,m+1):
        if A[i][j]<x:
            break
        if j==m:
            ansl.append(A[i][0])

if n==1:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for i,j in co(range(n),2):
    for k in range(1,m+1):
        if A[i][k]+A[j][k]<x:
            break
        if k==m:
            ansl.append(A[i][0]+A[j][0])
if n==2:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for i,j,k in co(range(n),3):
    for l in range(1,m+1):
        if A[i][l]+A[j][l]+A[k][l]<x:
            break
        if l==m:
            ansl.append(A[i][0]+A[j][0]+A[k][0])
if n==3:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for h,i,j,k in co(range(n),4):
    for l in range(1,m+1):
        if A[h][l]+A[i][l]+A[j][l]+A[k][l]<x:
            break
        if l==m:
            ansl.append(A[h][0]+A[i][0]+A[j][0]+A[k][0])
if n==4:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for g,h,i,j,k in co(range(n),5):
    for l in range(1,m+1):
        if sum([A[alp][l] for alp in [g,h,i,j,k]])<x:
            break
        if l==m:
            ansl.append(sum([A[alp][0] for alp in [g,h,i,j,k]]))
if n==5:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for f,g,h,i,j,k in co(range(n),6):
    for l in range(1,m+1):
        if sum([A[alp][l] for alp in [f,g,h,i,j,k]])<x:
            break
        if l==m:
            ansl.append(sum([A[alp][0] for alp in [f,g,h,i,j,k]]))
if n==6:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for e,f,g,h,i,j,k in co(range(n),7):
    for l in range(1,m+1):
        if sum([A[alp][l] for alp in [e,f,g,h,i,j,k]])<x:
            break
        if l==m:
            ansl.append(sum([A[alp][0] for alp in [e,f,g,h,i,j,k]]))
if n==7:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for d,e,f,g,h,i,j,k in co(range(n),8):
    for l in range(1,m+1):
        if sum([A[alp][l] for alp in [d,e,f,g,h,i,j,k]])<x:
            break
        if l==m:
            ansl.append(sum([A[alp][0] for alp in [d,e,f,g,h,i,j,k]]))
if n==8:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for c,d,e,f,g,h,i,j,k in co(range(n),9):
    for l in range(1,m+1):
        if sum([A[alp][l] for alp in [c,d,e,f,g,h,i,j,k]])<x:
            break
        if l==m:
            ansl.append(sum([A[alp][0] for alp in [c,d,e,f,g,h,i,j,k]]))
if n==9:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for b,c,d,e,f,g,h,i,j,k in co(range(n),10):
    for l in range(1,m+1):
        if sum([A[alp][l] for alp in [b,c,d,e,f,g,h,i,j,k]])<x:
            break
        if l==m:
            ansl.append(sum([A[alp][0] for alp in [b,c,d,e,f,g,h,i,j,k]]))
if n==10:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for a,b,c,d,e,f,g,h,i,j,k in co(range(n),11):
    for l in range(1,m+1):
        if sum([A[alp][l] for alp in [a,b,c,d,e,f,g,h,i,j,k]])<x:
            break
        if l==m:
            ansl.append(sum([A[alp][0] for alp in [a,b,c,d,e,f,g,h,i,j,k]]))
if n==11:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()
for a0,a,b,c,d,e,f,g,h,i,j,k in co(range(n),12):
    for l in range(1,m+1):
        if sum([A[alp][l] for alp in [a0,a,b,c,d,e,f,g,h,i,j,k]])<x:
            break
        if l==m:
            ansl.append(sum([A[alp][0] for alp in [a0,a,b,c,d,e,f,g,h,i,j,k]]))
if n==12:
    print(min(ansl) if len(ansl)>0 else "-1")
    quit()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[]
for _ in range(n):
    l.append(list(map(int,input().split())))
sum=100000000
for i in range(2**n):
    a=[0]*m
    buf=0
    for j in range(n):
        if (i>>j)&1:
            for k in range(m):
                a[k]+=l[j][k+1]
            buf+=l[j][0]
    flag=0
    for _ in a:
        if _<x:
            flag-=1
    if flag==0:
        sum=min(sum,buf)
if sum==100000000:
    print(-1)
else:
    print(sum)

Submission status: Accepted

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

	pay = float('inf')
	for i in range(1 << n):
		selected = []
		for j in range(n):
			if i >> j & 1:
				selected.append(j)
		rem = [0] * m
		tmp_pay = 0
		for j in selected:
			tmp_pay += books[j][0]
			for k in range(1, m+1):
				rem[k-1] += books[j][k]
		done = True
		for j in range(m):
			if rem[j] < x:
				done = False
		if done:
			pay = min(pay, tmp_pay)
	if pay == float('inf'):
		print(-1)
	else:
		print(pay)
resolve()

Submission status: Accepted

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

min_ = 10**10
for bit in range(1<<n):
    understanding = [0 for j in range(m)]
    c = 0
    for i in range(n):
        if bit & (1<<i):
            for k in range(m):
                understanding[k] += bag[i][k+1]
            c += bag[i][0]
            
    if all([a >= x for a in understanding] ):
        min_ = min(min_, c)
if min_ == 10**10:
    min_ = -1
print(min_)

Submission status: Accepted

Solution code:
# ----------------------------
N,M,X = map(int, input().split())
A = [list(map(int, input().split(" "))) for i in range(N)]
 
MOD = 10**9+7
a = [0]*M
value = [0]
ans = MOD
 
for i in range(2**N):
    for j in range(N+1):
        if(i >> j) & 1:
            for k in range(M):
                a[k] += A[j][k+1]
            value.append(A[j][0])
 
    if min(a) >= X :
        ans = min(ans,sum(value))
    a = [0]*M
    value = []
 
print(-1 if ans == MOD else ans)

Submission status: Accepted

Solution code:
import copy
n,m,x = map(int,input().split())
listA = []
for _ in range(n):
    listA.append(list(map(int,input().split())))
t = [[0 for i in range(n)]]
for i in range(n):
    l = len(t)
    for j in range(l):
        t.append(copy.copy(t[j]))
        t[len(t)-1][i] = 1
ans = float("inf")
for i in t:
    check = [0 for i in range(m+1)]
    for j in range(n):
        if i[j] == 1:
            for k in range(m+1):
                check[k] = check[k] + listA[j][k]
    an = 0
    for j in range(1,m+1):
        if check[j] < x:
            an += 1
    if an == 0:
        if ans > check[0]:
            ans = check[0]
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

import itertools
f=0
ans=sum
for i in itertools.product((1,0), repeat=n):
	X=[0]*(m+1)
	for j in range(n):
		if i[j]==1:
			for k in range(m+1):
				X[k]+=L[j][k]
	if min(X[1:])>=x:
		ans=min(ans,X[0])
		f+=1
if f==0:
	print(-1)
else:
	print(ans)

Submission status: Accepted

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

c_list = []
a_matrix = []

for i in range(n):
    items = list(map(int, input().split()))
    c_list.append(items[0])
    a_matrix.append(items[1:])

min_cost = 1000000 * (n+1)

for i in range(2**n):
    cost = 0
    skill_sum = [0 for _ in range(m)]
    bit_pattern = format(i, '0' + str(n) + 'b')[::-1]
    for i, a_line in enumerate(a_matrix):
        if bit_pattern[i] == "1":
            cost += c_list[i]
            for j, a in enumerate(a_line):
                skill_sum[j] += a
    
    if all(map(lambda skill_s: skill_s >= x, skill_sum)) and cost < min_cost:
        min_cost = cost

if min_cost >= 1000000 * (n+1):
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
nums = [int(e) for e in input().split()]
n = nums[0]
m = nums[1]
x = nums[2]

books = []
c = []

min_score = 100000000000000000000

for i in range(n):
    book = [int(e) for e in input().split()]
    c += book[:1]
    books += [book[1:]]

understand = [0] * m
noruma = [x] * m

def calc_understand(a):
    understand = [0] * m
    for i in range(n):
        for j in range(m):
            understand[j] += a[i] * books[i][j]
    return understand


def calc_score(a):
    score = 0
    for i in range(n):
        score += a[i] * c[i]
    return score

# 配列＊配列で全部がX以上になるn個の01からなる配列ができればよい
# DFS
def dfs(a):
    global count
    global min_score
    if len(a) == n+1:
        # トータル数と金額を出す
        understand = calc_understand(a[1:])
        understand.sort()
        if noruma <= understand:
            tmp_score = calc_score(a[1:])
            min_score = min(min_score, tmp_score)
        return

    a.append(0)
    while a[len(a) - 1] <= 1:
        dfs(a)
        a[len(a) - 1] += 1

    a.pop(-1)
    return

a = [0]
dfs(a)

if min_score < 100000000000000000000:
    print(min_score)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
import numpy as np
list=[list(input().split()) for _ in range(N)]
for i in range(N):
  for j in range(M+1):
    list[i][j]=int(list[i][j])

def bin(x):
  lists=[]
  k=0
  while x!=0:
    t=x%2
    lists.append(t)
    x=x//2
    k+=1
  for i in range(N-k):
    lists.append(0)
  return (lists)

def price(x):
  lists=list[:]
  listt=[]
  for i in range(N):
    lists[i]=lists[i]*bin(x)[i]
  for m in range(1,M+1):
    s=0
    for n in range(N):
      try:
        s+=lists[n][m]
      except IndexError:
        continue
    listt.append(s)
  p=1
  for i in range(M):
    if listt[i]<X:
      p=0
    else:
      continue
  S=0
  for k in range(N):
    try:
      S+=lists[k][0]
    except IndexError:
      continue
  return (S*p)

pr=0
for i in range(1,2**N):
  if pr==0:
    pr=max(pr,price(i))
  else:
    if price(i)>0:
      pr=min(pr,price(i))
    else:
      continue

if pr==0:
  print (-1)
else:
  print (pr)

Submission status: Accepted

Solution code:
import numpy as np

def main():
  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:])

  cost = np.inf

  for i in range(2**N):
    tmp_cost = 0
    skills = np.zeros(M)
    for j in range(N):
      if bin(i >> j)[-1] == '0':
        continue
      tmp_cost += C[j]
      skills = np.add(skills, np.array(A[j]))

    if (skills >= X).all() and tmp_cost<cost:
      cost = tmp_cost

  if cost == np.inf:
    print(-1)
  else:
    print(cost)







if __name__ == "__main__":
  main()

Submission status: Accepted

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

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

    ans = -1
    for bit in range(1 << N):
        cost = 0
        t = [0] * M
        for j in range(N):
            if (bit >> j) & 1:
                c, a = bk[j]
                cost += c
                for k in range(M):
                    t[k] += a[k]
            if all(x >= X for x in t):
                if (not ~ans) or (ans > cost):
                    ans = cost
    print(ans)


if __name__ == '__main__':
    main()