Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

0\leq A_{i, j} \leq 10^5

Input

Input is given from Standard Input in the following format:

N M X
C_1 A_{1,1} A_{1,2} \cdots A_{1,M}
C_2 A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
C_N A_{N,1} A_{N,2} \cdots A_{N,M}

Output

If the objective is not achievable, print -1; otherwise, print the minimum amount of money needed to achieve it.

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

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

min_cost=float('inf')
for i in range(2**n):
  flag=True
  cost_total=0
  a_total=[0]*m
  for j in range(n):
    if (i>>j)&1:
      cost_total+=c[j]
      for k in range(m):
        a_total[k]+=a[j][k]
  for s in range(m):
    if a_total[s]<x:flag=False
  if flag:
    min_cost=min(min_cost,cost_total)
  
if min_cost==float('inf'):
  print(-1)
else:
  print(min_cost)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = []
A = []
for _ in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)
ans = 10**18
for s in range(1<<N):
    an = 0
    L = [0] * M
    for i, (c, a) in enumerate(zip(C, A)):
        if s>>i&1:
            an += c
            for j, a_ in enumerate(a):
                L[j] += a_
    if all(l >= X for l in L):
        if an < ans:
            ans = an
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

# 購買する全パターンを回す
most_row_price = 10**10
for i in range(2**n):
    comb = str(bin(i)[2:]).zfill(n)
    
    # 購買パターン毎の購入金額と理解度を算出する
    understanding = [0] * m # 理解度の初期化
    total_money = 0 # 合計購入金額の初期化
    for j in range(n):
        
        # 購入しないケースは除外する
        if comb[j] == '0':
            continue
            
        # 購入するケースだけ、金額算出する
        total_money += ca[j][0]
        
        # 当該パターンの理解度を算出する
        for k in range(m):
            understanding[k] += ca[j][k+1]           

    for j in range(m):
        if understanding[j] < x:
            break
    else:
        most_row_price = min(total_money, most_row_price)

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

Submission status: Accepted

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

# 購買する全パターンを回す
most_row_price = 10**10
for i in range(2**n):
    comb = str(bin(i)[2:]).zfill(n)
    
    # 購買パターン毎の購入金額と理解度を算出する
    money_per_pattern = [0] * n # 購買パターン毎の金額の初期化
    understanding = [0] * m # 理解度の初期化
    total_money = 0 # 合計購入金額の初期化
    for j in range(n):
        
        # 購入しないケースは除外する
        if comb[j] == '0':
            continue
            
        # 購入するケースだけ、金額算出する
        money_per_pattern[j] = ca[j][0]
        
        # 当該パターンの理解度を算出する
        for k in range(m):
            understanding[k] += ca[j][k+1]           
    total_money = sum(money_per_pattern)            

    judge_flg = 'ok'
    for j in range(m):
        if understanding[j] < x:
            judge_flg = 'ng'
    
    if judge_flg == 'ok':
        most_row_price = min(total_money, most_row_price)

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

Submission status: Accepted

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

cost = []
for i in range(2**n):
    c_sum = 0
    u_sum = [0]*m
    for j in range(n):
        if (i>>j) & 1:
            c_sum += c[j]
            for k in range(m):
                u_sum[k] += algo[j][k]
    if all(s >= x for s in u_sum):
        cost.append(c_sum)
if cost:
    print(min(cost))
else:
    print(-1)

Submission status: Accepted

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

ans=inf=float('inf')
for perm in range(1,1<<N):
    tt,lvls=0,[0]*M
    for i in range(N):
        if perm&(1<<i)==0:
            continue
        tt+=C[i][0]
        for j in range(M):
            lvls[j]+=C[i][j+1]
        for j in range(M):
            if lvls[j]<X:
                break
        else:
            ans=min(ans,tt)
            break

print(ans if ans<inf else -1)

Submission status: Accepted

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

ans=inf=float('inf')
for perm in range(1,1<<N):
    tt,lvls=0,[0]*M
    for i in range(N):
        if perm&(1<<i)==0:
            continue
        tt+=C[i][0]
        for j in range(M):
            lvls[j]+=C[i][j+1]
        for j in range(M):
            if lvls[j]<X:
                break
        else:
            ans=min(ans,tt)
            break

print(ans if ans<inf else -1)

Submission status: Accepted

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

ans=inf=float('inf')
for p in range(1,1<<N):
    tt,lvls=0,[0]*M
    for i in range(N):
        if p&(1<<i)==0:
            continue
        tt+=C[i][0]
        for j in range(M):
            lvls[j]+=C[i][j+1]
        for j in range(M):
            if lvls[j]<X:
                break
        else:
            ans=min(ans,tt)
            break


print(ans if ans<inf else -1)

Submission status: Accepted

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

ans=inf=float('inf')
def dfs(idx,tt,l):
    global ans
    for i in range(idx,N):
        ntt=tt+C[i][0]
        nl=[l[j]+C[i][j+1] for j in range(M)]
        ok=True
        for x in nl:
            if x<X:
              ok=False
              break
        if ok:
            ans=min(ans,ntt)
        else:
	        dfs(i+1,ntt,nl)
        
dfs(0,0,[0]*M)

print(ans if ans<inf else -1)

Submission status: Accepted

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

costs = []

for i in range(1 << n): #全パターン
    cost = 0
    total = [0] * m #値段とm冊の本についてのリスト
    for j in range(n):
        if (i>>j) & 1 == 1 : #iをjだけ右にシフト。j冊目を買う場合
            cost += ca[j][0]
            for k in range(m):
                total[k] += ca[j][k+1]
    if all(total[l] >= x for l in range(m)):
        costs.append(cost)

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

Submission status: Accepted

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

ans=inf=float('inf')
def dfs(idx,tt,l):
    global ans
    for i in range(idx,N):
        ntt=tt+C[i][0]
        nl=[l[j]+C[i][j+1] for j in range(M)]
        for x in nl:
            if x<X: break
        else:
            ans=min(ans,ntt)
        dfs(i+1,ntt,nl)
        
dfs(0,0,[0]*M)

print(ans if ans<inf else -1)

Submission status: Accepted

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

mx=10**9
ans=mx
def dfs(i,tt,level):
    global ans
    if i==N:
        return
    tt+=C[i][0]
    lev=[]
    for j in range(M):
        lev.append(level[j]+C[i][j+1])
    ok=True
    for x in lev:
        if x<X:
            ok=False
            break
    if ok:
        ans=min(ans,tt)
    for j in range(i+1,N):
        dfs(j,tt,lev)
        

for i in range(N):
    dfs(i,0,[0]*M)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
minc=float("inf")

for i in range(2**n):
  lst=[0]*(m+1)
  for bit in range(n):
    if (i>>bit)&1==1:
      for ii,aa in enumerate(a[bit]):
        lst[ii]+=aa
  if min(lst[1:]) >= x:
    minc=min(minc,lst[0])
    
print(-1 if minc == float("inf") else minc)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
books = list(list(map(int,input().split())) for i in range(n))
mon_lis = []
for i in range(2**n):
    mon = 0
    exp = [0]*m
    check=[0]*m
    for j in range(n):
        if (i >> j) & 1:
            mon += books[j][0]
            for k in range(m):
                exp[k] += books[j][k+1]
    for k in range(m):
        if exp[k] >= x:
            check[k] = 1
    if not 0 in check:
        mon_lis.append(mon)
if not mon_lis:
    print(-1)
else:
    print(min(mon_lis))

Submission status: Accepted

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

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

min_money = -1

#n冊あるとき、2**n通りの選び方
count = 0
for i in range(2**n):
    select = format(count, "0" + str(n) + "b")
    lst = []
    # print(select)
    while "1" in select:
        index = select.index("1")
        lst.append(books[index])
        select = "0"*(index+1) + select[index+1:]
    # print(lst)
    for j in range(1,m+1):
        skill = sum([lst[k][j] for k in range(len(lst))])
        if skill < x:
            # print("skill" + str(j) + "sum" + str(skill))
            break
    else:
        sum_money = sum([lst[j][0] for j in range(len(lst))])
        if min_money != -1:
            min_money = min(min_money, sum_money)
        else:
            min_money = sum_money

    count += 1

print(min_money)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [list(map(int, input().split())) for i in range(N)]
ans = -1
for i in range(2 ** N):
    rikaido = [0 for k in range(M)]
    kingaku = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(M):
                rikaido[k] += C[j][k + 1]
            kingaku += C[j][0]
    if (min(rikaido) >= X) and (ans > kingaku or ans == -1):
        ans = kingaku
print(ans)

Submission status: Accepted

Solution code:
def backtrack(books, cur_book_ids, threshold, result):
    if len(cur_book_ids) > len(books):
        return
    if len(cur_book_ids) == len(books):
        achieved = True
        price_skills = [0] * len(books[0])
        for book,is_bought in zip(books, cur_book_ids):
            for j in range(len(book)):
                price_skills[j] += book[j]*is_bought
        for i in range(1, len(price_skills)):
            if price_skills[i] < threshold:
                achieved = False
        if achieved:
            if not result:
                result.append(price_skills[0])
            else:
                result[0] = min(result[0], price_skills[0])

    for i in (0,1):
        cur_book_ids.append(i)
        backtrack(books, cur_book_ids, threshold, result)
        cur_book_ids.pop()

def solve():
    N,M,X = [int(i) for i in input().split()]
    books = []
    for i in range(N):
        book = [int(i) for i in input().split()]
        books.append(book)
    result = []
    backtrack(books, [], X, result)
    if not result:
        print(-1)
    else:
        print(result[0])

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from itertools import product


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

ans = float("inf")
for buys in product((0, 1), repeat=N):
    cost = 0
    achivements = [0] * M
    for i, buy in enumerate(buys):
        if not buy:
            continue
        cost += C[i]
        for j in range(M):
            achivements[j] += A[i][j]
    if all(a >= X for a in achivements):
        ans = min(ans, cost)
print(ans) if ans != float("inf") else print(-1)

Submission status: Accepted

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

for i in range(2**N):
  A = [0 for _ in range(M+1)]
  for j in range(N):
    if i & (1<<j):
      for k in range(M+1):
        A[k] += C[j][k]
  flag = True
  for i in range(M):
    if A[i+1] < X:
      flag = False
  if flag:
    L.append(A[0])

if L == []:
  L.append(-1)
print(min(L))

Submission status: Accepted

Solution code:
from collections import deque
import numpy

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

stack = deque()
stack.appendleft((numpy.array([0] * M, dtype='int64'), 0, 0))

min_cost = 10**9

book_list = {}

while stack:
    info = stack.popleft()
    skill = info[0]
    cost = info[1]
    book_idx = info[2]

    if book_idx < N:
        if book_idx in book_list:
            book = book_list[book_idx]
        else:
            book = numpy.array([int(x)
                                for x in input().split()], dtype='int64')
            book_list[book_idx] = book

        after_skill = skill + book[1:]
        after_cost = cost+book[0]

        stack.appendleft((after_skill, after_cost, book_idx+1))
        stack.appendleft((skill, cost, book_idx+1))

    else:
        if cost < min_cost:
            if numpy.all(skill >= X):
                min_cost = cost

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(N)]
ans = -1
for i in range(1 << N):
    rikai = [0]*M
    buy = 0
    ok=1
    for j in range(N):
        if (i >> j) & 1:
            for k in range(M):
                rikai[k] += CA[j-1][k+1]
            buy += CA[j-1][0]
    for a in rikai:
        if a >= X:
            continue
        else:
            ok=0
            break
    if ok==1:
        if ans == -1:
            ans = buy
        else:
            ans = min(ans, buy)
print(ans)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m,x = readInts()
C = [readInts() for _ in range(n)]
INF = float('inf')
ans = INF
for bit in range(1 << n):
    all = [0] * m
    money = 0
    for i in range(n):
        if bit & (1 << i):
            money += C[i][0]
            for j in range(m):
                all[j] += C[i][j+1]
    flag = True
    for k in range(m):
        if all[k] >= x:
            pass
        else:
            flag = False
            break
    if flag:
        ans = min(ans, money)
print(ans if ans != INF else '-1')

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
cl = []
al = []
for i in range(n):
    l = list(map(int, input().split()))
    cl.append(l[0])
    al.append(l[1:])
result = -1
for i in range(1<<n):
    price = 0
    unders = [0] * m
    for j in range(n):
        if((i>>j & 1) == 1):
            price+=cl[j]
            for k in range(m):
                unders[k] += al[j][k]
    for j in unders:
        if(j < x):
            break
    else:
        if(result == -1):
            result = price
        else:
            result= min(result, price)
                
print(result)

Submission status: Accepted

Solution code:
from itertools import product
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
C = []
for i in range(N):
    C.append(A[i].pop(0))
ans = sum(C)+10
for x in product((0,1),repeat=N):
    flag = 0
    for j in range(M):
        cnt = 0
        for i in range(N):
            if x[i]==1:
                cnt += A[i][j]
        if cnt<X:
            flag = 1
            break
    if flag==0:
        tot = 0
        for i in range(N):
            if x[i]==1:
                tot += C[i]
        ans = min(ans,tot)
if ans>sum(C):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ans = []
for i in range(2**n):
    pat = [0] * n #買うかどうか
    r = [0] * m #理解度
    money = 0
    for j in range(n):
        if ((i>>j)&1):
            pat[n-1-j] = 1
    for x in range(len(pat)):
        if pat[x] == 1:
            money += a[x][0]
            for y in range(m):
                r[y] += a[x][y+1]
    flag = True
    for z in range(m):
        if r[z] < X:
            flag = False
            break
    if flag:
        ans.append(money)
print(min(ans) if ans else -1)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, M, X, CA):
    ans = 10**10
    for p in range(1 << N):
        AA = [0] * (M + 1)
        C = 0
        for i in range(N):
            if p & (1 << i):
                C += CA[i][0]
                for j in range(1, M + 1):
                    AA[j] += CA[i][j]
        for i in range(1, M + 1):
            if AA[i] < X:
                break
        else:
            ans = min(ans, C)
    print(ans if ans < 10**10 else -1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M, X = map(int, input().split())
    CA = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, M, X, CA)

Submission status: Accepted

Solution code:
INF = 10**9 + 7


def main():
    N, M, X = (int(i) for i in input().split())
    CA = [[int(i) for i in input().split()] for j in range(N)]
    ans = INF
    for bit in range(1 << N):
        wakaru = [0]*M
        cur = 0
        for i in range(N):
            if bit & (1 << i):
                c, *A = CA[i]
                cur += c
                for j in range(M):
                    wakaru[j] += A[j]
        if all(m >= X for m in wakaru):
            ans = min(ans, cur)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

al = []
cl = []
for _ in range(n):
    row = list(map(int, input().split())) 
    cl.append(row[0])
    al.append(row[1:])


ans = 10**9
bit = 2
ite = list(product(range(bit),repeat=n))
for pattern in ite:
    skills = [0]*m
    cost = 0
    for i, v in enumerate(pattern):
        if v == 1:
            curr_al = al[i]
            cost += cl[i]
            for j, a in enumerate(curr_al):
                skills[j] += a
    if min(skills) >= x:
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = []
A = []
for i in range(n):
    temp = list(map(int, input().split()))
    c = temp[0]
    a = temp[1:]
    A.append(a)
    C.append(c)

ans = 10**18
for i in range(2**n):
    s = [0]*m
    temp = 0
    for j in range(n):
        if (i >> j) & 1:
            temp += C[j]
            for k in range(m):
                s[k] += A[j][k]
    flag = True
    for l in range(m):
        if s[l] < x:
            flag = False
    if flag:
        ans = min(ans, temp)
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
 #15858750
n, m, x = map(int, input().split()) 
a = [list(map(int, input().split())) for i in range(n)]
ans = 12*(10**5) + 1

for j in range(2**n):  
    mlist = [0]*m 
    money = 0
    for k in range(n): 
        if (j >> k) & 1 == 1:
            money += a[k][0]
            for l in range(1, m+1): 
                mlist[l-1] += a[k][l]
    if min(mlist) >= x:
        ans = min(ans, money)
        
if ans == 12*(10**5) + 1 :
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

def python_list_add(in1, in2):
   return list(map(sum, zip(in1, in2)))

N, M, X = map(int, input().split())
T = []
C = []
min = 10000000

for n in range(N):
    C.append(list(map(int, input().split())))

for bi in range(2**N):
    rikai = [0]*(M+1)
    low = False
    for i in range(N):
        b = 2**i
        if bi & b != 0:
            for j in range(M+1):
                rikai[j] = rikai[j] + C[i][j]
                #if rikai[0] > min:
                    #break
    #print(rikai)
    if rikai[0] < min:
        for m in range(1, M+1):
            if rikai[m] < X:
                low = True
                #print('low rikai')
                break
        if low == False:
            min = rikai[0]
if min == 10000000:
    print('-1')
else:
    print(min)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
B=[list(map(int,input().split())) for _ in range(N)]
inf=(10**5)*12+1
ans=inf
for i in range(1,2**N):
  tmp=[0]*M
  c=0
  for j in range(N):
    if i>>j&1:
      for k in range(M):
        tmp[k]+=B[j][k+1]
      c+=B[j][0]
  if len([i for i in tmp if i>=X])==M:
    ans=min(c,ans)
print(ans if ans<inf else -1)

Submission status: Accepted

Solution code:
def check(times):
  for i in range(m):
    if times[i] < x:
      return False
  else:
    return True

n, m, x = map(int, input().split())
c = [0] * n
a = [0] * n
for i in range(n):
  c[i], *a[i] = list(map(int, input().split()))
   
ans = 10**10
for i in range(2**n):
  times = [0] * m
  cnt = 0
  money = 0
  while i > 0:
    if i & 1:
      for j in range(m):
        times[j] += a[cnt][j]
      money += c[cnt]
    i = i >> 1
    cnt += 1
  if check(times):
    ans = min(money, ans)
if ans == 10**10:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
from itertools import product as prod
N,M,X=map(int,input().split())
B=[list(map(int,input().split())) for _ in range(N)]
ans=float('INF')
for v in prod(range(2),repeat=N):
  scores=[0]*M
  cost=0
  for i in range(N):
    if v[i]==1:
      cost+=B[i][0]
      for j in range(M):
        scores[j]+=B[i][1+j]
  if min(scores)>=X:
    ans=min(ans,cost)

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

Submission status: Accepted

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

A=[0]*N
for j in range(N):
    A[j]=[int(x) for x in input().split()]
money=10**7
for i in range(2**N):
    read=[0]*N #その本を読むか否か
    for h in range(N):
        if i%2==1:
            read[h]=1
        i//=2
    understanding=[0]*M
    kouho=0
    for k in range(N):
        if read[k]==1:
            kouho+=A[k][0]
            for m in range(1,M+1):
                understanding[m-1]+=A[k][m]
    if min(understanding)>=X:
        money=min(money,kouho)
if money==10**7:
    print(-1)
else:
    print(money)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import itertools
import numpy as np

def main():
    
    N, M, X = map(int, input().split())
    for i in range(N):
        row = np.array(list(map(int, input().split())))
        # print(row)
        if i == 0:
            c_array = row[0].reshape(1, 1)
            a_matrix = row[1:].reshape(1, len(row[1:]))
        else:
            c_array = np.append(c_array, row[0])
            a_matrix = np.vstack([a_matrix, row[1:].reshape(1, len(row[1:]))])
    # print(c_array)
    # print(a_matrix)
    min_cost = float("inf")
    for i in range(1, N+1):
        for v in itertools.combinations(np.arange(N), i):
            tmp = a_matrix[v, :].sum(axis=0)
            cost = c_array[list(v)].sum()
            # print(tmp)
            if tmp.min() >= X and cost <= min_cost:
                min_cost = cost
                
    if min_cost == float("inf"):
        print("-1")
    else:
        print(min_cost)
    
main()

Submission status: Accepted

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

# 参考書の組み合わせ
price_min = pow(10, 6) * n
found = False
for bits in range(2 ** n):
    level = [0] * m
    price = 0
    # ビットが立っている参考書の理解度と値段を加算
    for book in range(n):
        if (bits >> book) & 1:
            price += books[book][0]
            for alg in range(m):
                level[alg] += books[book][alg + 1]
    # 理解度がXに満たないアルゴリズムを抽出
    level = list(filter(lambda lv: lv < x, level))
    # 理解度の条件を満たし、かつ合計額が最低値を下回るときに最低値を更新
    if len(level) == 0 and price < price_min:
        found = True
        price_min = price
print(price_min if found else "-1")

Submission status: Accepted

Solution code:
import itertools


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

    flag1 = True
    max_lst = []
    for i in range(m):
        understanding = 0
        for j in range(n):
            understanding += lst[j][i+1]
        max_lst.append(understanding)

    for i in range(len(max_lst)):
        maximum = max_lst[i]
        if maximum < x:
            cost = -1
            flag1 = False
            break

    if flag1:
        number = 1
        cost_lst = []
        while number <= n:   ##一冊laからどんどん増やす
            n_lst = []
            for i in range(n):
                n_lst.append(i)
            choice = list(itertools.combinations(n_lst, number))
            combination_number = len(choice)
            choice_number = len(choice[0])

            for i in range(combination_number):

                cost1 = 0
                understanding_lst = [0] * m
                for j in range(choice_number):  ##一組終了
                    choiced_number = choice[i][j]
                    cost1 += lst[choiced_number][0]

                    for k in range(1, m + 1):
                        unstg = lst[choiced_number][k]
                        understanding_lst[k - 1] += unstg

                over_x = 0
                for l in range(m):
                    understanding = understanding_lst[l]
                    if understanding >= x:
                        over_x += 1

                if over_x == m:
                    cost_lst.append(cost1)

            number += 1

        cost = min(cost_lst)

    print(cost)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m, x = MAP()
c = []
a = []
for i in range(n):
    A = LIST()
    c.append(A[0])
    a.append(A[1:])
ans = inf
for y in product([0,1], repeat=n):
    b = [0]*m
    tmp = 0
    for i in range(n):
        if y[i] == 1:
            tmp += c[i]
            for j in range(m):
                b[j] += a[i][j]
            if all(b[k]>=x for k in range(m)):
                ans = min(ans, tmp)
if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
number=list(map(int,input().split()))
N,M,X=number[0],number[1],number[2]
price=0
nums=[]
for i in range(N):
    tmp=list(map(int,input().split()))
    nums.append(tmp)
target=[0 for i in range(M)]
answer=10000000
for cowmask in range(1<<N):
        price=0
        target=[0 for k in range(M)]
        for x in range(N):
                if (cowmask>>x)&1==0:
                    price+=nums[x][0]
                    for j in range(1,M+1):
                        target[j-1]+=nums[x][j]
        if min(target)>=X:
            answer=min(answer,price)

if answer==10000000:
    print(-1)
else:
    print(answer)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split()) 
a = [list(map(int, input().split())) for i in range(n)]
ans = 12*(10**5) + 1
for j in range(2**n):  
    mlist = [0]*m 
    money = 0
    for k in range(n): 
        if (j >> k) & 1 == 1:
            money += a[k][0]
            for l in range(1, m+1): 
                mlist[l-1] += a[k][l]
    if min(mlist) >= x:
        ans = min(ans, money)
if ans == 12*(10**5) + 1 :
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m,x = map(int, input().split())
result_list = [[0 for i in range(m+1)] for i in range(2**n)]
book_list=[]
zero_one = [0,1]
combi_list = list(itertools.product(zero_one, repeat=n))
for i in range(n):
    can = list(map(int, input().split()))
    book_list.append(can)
#2^n通りの組み合わせ
for i in range(2**n):
    #n個全部足す
    for j in range(n):
        #価格とスキルを全部足す
        for k in range(m+1):
            result_list[i][k] +=  book_list[j][k] * combi_list[i][j]
Ans_list = []
for i in range(len(result_list)):
    kari_list = result_list[i][1:]
    if min(kari_list) >= x:
        Ans_list.append(result_list[i][0])
if Ans_list == []:
    print(-1)
else:
    Ans = min(Ans_list)
    print(Ans)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = list(map(int, input().split()))
masu = [list(map(int, input().split())) for _ in range(n)]
price = [masu[i][0] for i in range(n)]
skills = [masu[i][1:] for i in range(n)]



ans = 100000000000000
for idx_n in range(2**n):
    skill_sets = np.array([0 for _ in range(m)])
    total = 0
    #print(skill_sets.shape)
    for i_row, row in enumerate(skills):
        if idx_n & (2**i_row) >0:
            total += price[i_row]
            #print(np.array(row).shape)
            skill_sets += np.array(row)
    #print(skill_sets)
    if skill_sets.min() >= x:
        if ans >= total:
            ans = total
if ans == 100000000000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for n in range(N)]
a = 10**9

for i in range(2**N):
  S = (M+1)*[0]
  for j in range(N):
    if (i>>j)&1:
      S = [S[k]+A[j][k] for k in range(M+1)]
  if all([X<=s for s in S[1:]]):
    a = min(a,S[0])

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