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())
goods = [list(map(int,input().split())) for i in range(n)]
from itertools import combinations as comb
minm=float('INF')
def check(l):
    suml = [0]*(m+1)
    for j in l:
        good = goods[j]
        for s in range(0,m+1):
            suml[s] += good[s]
    for j in range(1,m+1):
        if(suml[j]<x):
            return None
    return suml[0]

ok = False
for i in range(1,n+1):
    
    for l in comb(range(n),i):
        num = check(l)
        if(num is None):
            continue
        if(minm>num):
            minm = num
            ok = True
if(ok):
    print(minm)
else:
    print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
n,m,x = [int(x) for x in stdin.readline().rstrip().split()]
a = []
for i in range(n):
    a.append([int(x) for x in stdin.readline().rstrip().split()])
k = list(itertools.product(range(0,2), repeat=n))
ans = -1
for i in range(len(k)):
    b = [0]*m
    money = 0
    o = 1
    for j in range(n):
        if k[i][j] == 1:
            for l in range(m):
                b[l] += a[j][l+1]
            money += a[j][0]
    for j in range(m):
        if b[j] < x:
            o = 0
            break
    if o == 1:
        if ans == -1:
            ans = money
        else:
            ans = min(ans,money)
print(ans)

Submission status: Accepted

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

ans = []

for i in range(2 ** n):
    jud = [0]*m
    money = 0
    for j in range(n):
        if (i >> j) & 1:
            money += ca[j][0]
            for k in range(m):
                jud[k] += ca[j][k+1]
    if min(jud) >= x:
        ans.append(money)

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

Submission status: Accepted

Solution code:


def main():
    N, M, X = [int(x) for x in input().split()]
    CA = [[int(x) for x in input().split()] for _ in range(N)]
    C = [CA[i][0] for i in range(N)]
    A = [CA[i][1:] for i in range(N)]

    def calc(bit):
        i = 0
        rikai = [0] * M
        cost = 0
        while bit > 0:
            if bit & 1:
                cost += C[i]
                for j in range(M):
                    rikai[j] += A[i][j]
            bit = bit >> 1
            i += 1
        if all(r >= X for r in rikai):
            return cost
        else:
            return None

    bit = 1
    ans = float("inf")
    while bit <= (2**N-1):
        cost = calc(bit)
        if cost is not None:
            ans = min(ans, cost)
        bit += 1
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 13*10**5
for b in range(2**n):
    bit=[0]*n
    for i in range(n):      
        bit[i]=b%2
        b//=2 
    bit = np.array(bit).astype(bool)
    if bit.sum()==0:
      continue
    score = book[bit].sum(axis=0)
    if (score[1:] < x).sum() == 0:
      if ans > score[0]:
        ans = score[0]
if ans == 13*10**5:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import itertools


def main():
  N, M, X = map(int, input().split(' '))
  mat = np.array([list(map(int, input().split(' '))) for _ in range(N)])

  INT_MAX = 100000000
  min_c = INT_MAX
  for conds in itertools.product([0, 1], repeat=N):
    result = np.dot(conds, mat)
    skills = result[1:]
    if np.all(skills >= X):
      min_c = min(min_c, result[0])

  print(min_c if min_c < INT_MAX else -1)


if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

book_list.sort(key=lambda el: el[0])  # 価格でソート

# 金額の最小値
ans = 1e10

for bit in range(1 << n):
    # 全アルゴリズムの理解度
    algo_val = [0 for _ in range(m)]
    # 金額
    ans_tmp = 0

    # 全アルゴリズムの理解度がxを超える
    for i, book in enumerate(book_list):
        if (bit & (1 << i)):
            ans_tmp += book[0]
            for j, a in enumerate(book[1:]):
                algo_val[j] += a

    if all(i >= x for i in algo_val):
        # その中で最小のもの
        ans = min(ans_tmp, ans)

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

Submission status: Accepted

Solution code:
import numpy as np
n,m,x =map(int,input().split())
syo = []
for _ in range(n):
    temp =list(map(int,input().split()))
    syo.append(temp)

ans = []

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

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

Submission status: Accepted

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

q = set()
q.add(tuple([0] * (m+1)))

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

    update = set()
    for qq in q:
        l = list(qq)
        l[0] = qq[0] + c[0]
        for i in range(1, m+1):
            l[i] = min(qq[i] + c[i], x)
        update.add(tuple(l))

    q.update(update)

max_ans = 10 ** 5 * 13
ans = max_ans
for qq in q:
    if qq[0] < ans and sum(qq[1:]) == m * x:
        ans = qq[0]

if ans < max_ans:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

ans=10000000000000000000000000000

for dummy in range(2**n):
  books=format(dummy, 'b')
  books='0'*(n-len(books))+books
  point=[0]*(m+1)
  cost=0
  for i in range(n):
    if books[i]=='1':
      cost+=cx[i][0]
      for j in range(1,m+1):
        point[j]+=cx[i][j]
  ok=1
  for j in range(1,m+1):
    if point[j]<x:
      ok=0
  if ok:
    ans=min(ans,cost)


if ans==10000000000000000000000000000:
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m, x = map(int, input().split())
a = [0]*n
for i in range(n):
    a[i] = list(map(int, input().split()))

result = -1
for i in range(2**n):
    rikai = [0]*m
    cost = 0
    # print(bin(i))
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m):
                rikai[k] += a[j][k+1]
            cost += a[j][0]
        # print(rikai)
    satisfied = True
    for rj in rikai:
        if rj < x:
            satisfied = False
            break

    if result == -1:
        if satisfied:
            result = cost
    else:
        if satisfied & (cost<result):
            result = cost

print (result)

Submission status: Accepted

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

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

minyen = float("inf")
for i in range(2**N):
    flag = False
    hoji = []
    rikai = [0]*M
    #print("pattern{}: ".format(i), end="")
    for j in range(N):
        if((i>>j)&1):
            hoji.append(hon[j][0])  # フラグが立っていたら bag に果物を詰める
            for k in range(M):
                rikai[k] += hon[j][k+1]

    for k in range(M):
        if X > rikai[k]:
            flag = True
            break

    if flag:
        continue
    else:
        minyen = min(minyen,sum(hoji))

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M,X=map(int,input().split())
CA=[]
for i in range(N):
  CA.append(list(map(int,input().split())))
money=9000000000
count=1
for i in range(1,N+1):
  test=itertools.combinations(CA,i)
  for j in test:#組み合わせごとに計算
    pre_ans=np.sum(j, axis=0)
    if pre_ans[0]<money and np.all(pre_ans[1:]>=X):
      money=pre_ans[0]
      count=0
if count==0:
  print(money)
else:
  print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input('').split(' '))
c=[]
a=[]
for k in range(n):
    s=input('')
    s=s.split(' ')

    c.append(int(s[0]))
    kara=[]
    for l in range(len(s)-1):
        kara.append(int(s[l+1]))
    
    a.append(kara)

b=[]
for k in range(n):
    b.append(0)

lx=[]
for k in range(m):
    lx.append(0)

able=0
mcos=100000000000000000
while b[n-1]!=2:
    cost=0

    for k in range(m):
        lx[k]=0
    
    for k in range(n):
        if b[k]==1:
            for j in range(m):
                lx[j]+=a[k][j]
            cost+=c[k]
    
    ok=1
    for k in range(m):
        if lx[k]>=x:
            ok=ok*1
        else:
            ok=ok*0
        
    if ok==1 and cost<=mcos:
        able=1
        mcos=cost
    
    b[0]+=1
    for k in range(n-1):
        if b[k]==2:
            b[k]=0
            b[k+1]+=1

if able==1:
    print(mcos)
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m, x = mi()
    cost = []
    effect = []
    for _ in range(n):
        line = lmi()
        cost.append(line[0])
        effect.append(line[1:])

    ans = 10 ** 10
    for p in product([True, False], repeat=n):    # 2^n
        price = 0
        improved = [0] * m
        for i in range(len(p)):    # n
            if p[i]:
                price += cost[i]
                for j in range(len(effect[i])):    # m
                    improved[j] += effect[i][j]
        # print(p)
        # print(price)
        # print(improved)
        if all(map(lambda imp: imp >= x, improved)):
            ans = min(ans, price) 
            # print('updated')
    print(ans) if ans != 10**10 else print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
from sys import stdin


def main():
    N, M, X = [int(x) for x in stdin.readline().rstrip().split()]
    CAs = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
    ans = 100100100100100
    for n in range(1, N + 1):
        for comb in combinations(range(1, N + 1), n):
            tmp = [0] * (M + 1)
            for c in comb:
                for i in range(len(tmp)):
                    tmp[i] += CAs[c - 1][i]
            if len([x for x in tmp[1:] if X <= x]) == M:
                ans = min(ans, tmp[0])
    if ans == 100100100100100:
        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())
books = [[int(j) for j in input().split()] for i in range(n)]
min_cost = float('inf')
for bit in product([0, 1], repeat=n):
    cost = 0
    skill = [0] * m
    for i, b in enumerate(bit):
        if b == 1:
            cost += books[i][0]
            for j in range(m):
                skill[j] += books[i][j + 1]
    if x <= min(i for i in skill):
        min_cost = min(min_cost, cost)
print(min_cost if min_cost != float('inf') else -1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 21:06:30 2020

@author: shinba
"""
n,m,x = map(int,input().split())

ca = []
for i in range(n):
    ca.append(list(map(int,input().split())))
    
ans = float("inf")
for i in range(1,2**n):
    s = [0]*(m+1) 
    for j in range(n):
        if (i>>j) & 1:
            s[0] += ca[j][0]
            for k in range(1,m+1):
                s[k] += ca[j][k]
    if s[0] < ans:
        for i in range(1,m+1):
            if s[i] < x:
                break
        else:
            ans = s[0]

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

Submission status: Accepted

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

costs = [0]*n
values = []

for i in range(n):
    v = list(map(int, input().split()))
    costs[i] = v[0]
    values.append(v[1:])

candidates = []
for i in range(pow(2, n)):

    learning = [0]*m
    currentCost = 0
    for bit in range(n):
        select = i >> bit & 1
        if select == 1:
            currentCost += costs[bit]
            for j, v in enumerate(values[bit]):
                learning[j] += v

    if all([l >= x for l in learning]):
        candidates.append(currentCost)

print((-1 if len(candidates) == 0 else min(candidates)))

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = -1

for j in range(1, N+1):
    for i in combinations(box, j):
        kakaku = 0
        rika = [0 for _ in range(M)]
        for el in i:
            kakaku += el[0]
            for n, k in enumerate(el[1:]):
                rika[n] += k

        if all(p >= X for p in rika):
            if ans == -1:
                ans = kakaku
            else:
                ans = min(kakaku, ans)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
def main():

    n,m,x = tuple([int(t)for t in input().split()])

    a = [np.array([int(t)for t in input().split()])for _ in [0]*n]
    candidate = []
    for i in range(n):
        for data in itertools.combinations(a,i+1):
            data = sum(data)
            if np.all(data[1:]>=x):
                candidate.append(data[0])
    if len(candidate)==0:
        print(-1)
    else:
        print(min(candidate))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

C=[]
A=[]
for i in range(N):
    tCA=list(map(int,input().split(' ')))
    C.append(tCA[0])
    A.append(tCA[1:M+1])
maxCost=10**8
minCost=maxCost

#print(A)
for i in range(2**N):
    binstr=format(i,'0'+str(N)+'b')
    #print(binstr)
    tmpM=[]
    for t in range(M):
        tmpM.append(0)
    tmpCost=0
    for n in range(N):
        if binstr[n]=='1':
            tmpCost+=C[n]
            for m in range(M):
                #print(n,m)
                tmpM[m]+=A[n][m]
    #print(tmpM)
    #print(tmpCost)
    #check X
    flg = True
    for m in range(M):
        if tmpM[m] < X:
            flg=False
    if flg:
        minCost=min(minCost,tmpCost)

if minCost==maxCost:
    print(-1)
else:
    print(minCost)

Submission status: Accepted

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

ans=[]
for i in range(2**n):
	A=[0]*m
	C=0
	lst=list(map(int,format(i,'b').zfill(n)))
	for j in range(n):
		if lst[j]==1:
			C+=c[j]
			for k in range(m):
				A[k]+=a[j][k]
	if all(elem>=x for elem in A):
		ans.append(C)
if len(ans):
	print(min(ans))
else:
	print(-1)

Submission status: Accepted

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

bestcost = 9999999999
for i in range(pow(2,n)):
    ability = [0]*m
    cost = 0
    num = i
    k = n-1
    while k >= 0:
        if num // pow(2,k) == 1:
            cost += books[k][0]
            for j in range(m):
                ability[j] += books[k][j+1]
            num -= pow(2,k)
        k -= 1
    
    for j in range(m):
        if ability[j] < x:
            cost = 9999999999
    bestcost = min(cost, bestcost)
    

if bestcost == 9999999999:
    print(-1)
else:
    print(bestcost)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
ans=10**10
f=1
s=[list(map(int,input().split())) for _ in range(n)]
for i in range(1<<n):
  t=np.zeros(m+1)
  for j in range(n):
    if (i>>j)&1:
      t=t+np.array(s[j])
  if all(t[1:]>=x):
    ans=min(t[0],ans)
    f=0
if f:
  print(-1)
else:
  print(int(ans))

Submission status: Accepted

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

cost = []
for i in range(2**N):
    cst = 0
    alg = [0 for _ in range(M)]
    Flg = True
    for j in range(N):
        if((i >> j) & 1):
            cst += lst[j][0]
            for k in range(1, M+1):
                alg[k-1] += lst[j][k]
    
    for a in alg:
        if(a < X):
            Flg = False
    if(Flg):
        cost.append(cst)
    
if(len(cost) > 0):
    print(min(cost))
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# sys.stdin.readline()

import sys
import numpy as np
input = sys.stdin.readline
#n = int(input())
#n,k = map(int,input().split())
#A = list(map(int,input().split()))
#s=input()
#a = input()
n,m,x = map(int,input().split())
A = np.array([list(map(int,input().split())) for _ in range(n)])
ans = 10**8
for i in range(1,2 ** n):
    bag = np.array([])
    total = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
              # フラグが立っていたら bag に果物を詰める
            total += A[j]
            
              # 買い物累計額にも加算

    if x <= min(list(total[1::])):
        ans = min(ans , total[0])

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n,m,x = map(int,input().split())
#c = [0 for _ in range(n)]
a = []

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

a = np.array(a)

lis = list(itertools.product([0,1],repeat=n))
mon = [10**8 for i in range(n)]
mi = 10**8

for i in lis:
    sum = [0 for _ in range(m+1)]
    hantei = 0
    for ind,j in enumerate(i):
        if j==1:
            sum += a[ind]

    for m in range(1,m+1):
        if sum[m]<x:
            hantei = 1
    if hantei == 0:
        mi = min(mi,sum[0])
if mi == 10**8:
    print(-1)
else:
    print(mi)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations


n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]
n_idx = [i for i in range(1, n+1)]
price_lst = []
for i in range(1, n+1):
    idx_lst = list(combinations(n_idx, i))
    for idx_tup in idx_lst:
        ans = np.array([0] * m)
        price = 0
        for idx in idx_tup:
            ans += np.array(ca[idx-1][1:])
            price += ca[idx-1][0]
        if all(ans >= x):
            price_lst.append(price)
if len(price_lst) > 0:
    print(min(price_lst))
else:
    print(-1)

Submission status: Accepted

Solution code:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M,X = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(N)]
rows = np.array(rows)

ans = 10**5 * N +1
for bitlines in range(0,1<<N):
    tmp = np.array([0]*(M+1))
    for target in range(N):
        if bitlines>>target & 1:
            tmp = tmp + rows[target]
        else:
            continue
    if np.bincount((tmp>=X)[1:],minlength=2)[1]==M:
        ans = min(ans,tmp[0])

if ans == 10**5 * N +1:
    ans = -1

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Accepted

Solution code:
import itertools
import copy
n,m,x = map(int,input().split())
ans = [0 for i in range(m)]
books = []
answer = 1000000000000000000000
for i in range(n):
    books.append(list(map(int,input().split())))
for i in range(n):
    stock = list(list(itertools.combinations([num for num in range(n)], i+1)))
    for j in stock:
        cost = 0
        ans = [0 for i in range(m)]
        for k in j:
            for e,l in enumerate(books[k]):
                if e == 0:
                    cost += l
                else:
                    ans[e-1] += l
            if min(ans) >= x and cost < answer:
                answer = copy.deepcopy(cost)
if answer == 1000000000000000000000:
    print(-1)
else:
    print(answer)

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
list_CA = [ list(map(int,input().split(" "))) for i in range(n)]
l = [i for i in range(1, n+1)]
ans = pow(10, 9)
for i in range(1, n+1):
    k = list(itertools.combinations(l, i))
    for j in range(len(k)):
        h = [0]*m
        cnt = 0
        for q in k[j]:
            for g in range(m):
                h[g] += list_CA[q-1][g+1]
            cnt += list_CA[q-1][0]
        c = 0
        for v in h:
            if v >= x:
                c += 1
        if c == m:
            ans = min(cnt, ans)

if ans == pow(10, 9):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
"""
learn M algorithms
all start at level 0
N books on algorithms
i-th book sold for C_i yen
understanding increase by A_i_j where j is the j-th algorithm

Goal: X or higher understanding for all M algorithms
MINIMIZE YEN USED
"""

def x_satisfied(cur_und, x):
    for val in cur_und:
        if val < x:
            return False
    return True

def copy_update(cur_und, matrix, item_num):
    cur_und = cur_und[::]

    for i, lvl in enumerate(matrix[item_num]):
        cur_und[i] += lvl
    
    return cur_und




def solve(n, m, x, cost, matrix):
    def rec_solve(item_num, cur_cost, cur_und):
        nonlocal cost, matrix, n, m, x

        if x_satisfied(cur_und, x):
            return cur_cost
        elif item_num == n:
            return float("inf")
        
        #print(item_num, cur_cost, cur_und)
        #print(cost[item_num])
        take = rec_solve(item_num + 1, cur_cost + cost[item_num], copy_update(cur_und, matrix, item_num))
        dont = rec_solve(item_num + 1, cur_cost, cur_und)

        return min(take, dont)

    return rec_solve(0,0, [0] * m)


N, M, X = map(int, input().split())
cost = []
matrix = []

for _ in range(N):
    row = []
    inp = map(int, input().split())
    cost.append(next(inp))
    for i in inp:
        row.append(i)
    matrix.append(row)

res = solve(N, M, X, cost, matrix)
if res == float("inf"):
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
# C

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

import numpy as np
Cs = np.array([ca[0] for ca in CAs])
As = [np.array(ca[1:]) for ca in CAs]

import itertools
states = list(itertools.product([True, False], repeat=N))

def compute(state):
    arr = np.array([0] * M)
    for i in range(N):
        arr += As[i] * state[i]
    price = (Cs * state).sum() if ((arr >= X).sum() == M) else -1
    return price


res = np.array(list(map(compute, states)))
res = res[res > 0]
print(min(res) if len(res) > 0 else -1)

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = [int(x) for x in input().split()]
books = []
ans = 10 ** 7
for i in range(N):
  books.append([int(x) for x in input().split()])
books = np.array(books)
for i in range(1,2**N):
  t = np.array([0]*(M+1))
  for j in range(N):
    if i & 1 == 1:
      t = t + books[j]
    i = i >> 1
  s = min(t[1:])
  if min(t[1:]) >= X:
    if t[0] < ans:
      ans = t[0]
  #print(ans)
if ans == 10 ** 7:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
# C - Skill Up

import itertools
import numpy as np
N, M, X = map(int, input().split())
CA = np.zeros((N, M+1), dtype=np.int64)
for i in range(N):
    CA[i] = list(int(x) for x in input().split())

ans = 10**18
for lst in itertools.product((0,1), repeat=N):
    tmp = 0
    pnt = np.zeros(M, dtype=np.int64)
    for i in range(N):
        if lst[i] == 1:
            tmp += CA[i][0]
            pnt += CA[i][1:]
            if np.all(pnt >= X):
                ans = min(ans, tmp)

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

Submission status: Accepted

Solution code:
# coding:utf-8
import itertools

N, M, X = map(int, input().split(' '))
books = []
ans = (10 ** 5) * N + 1

maximum = [0 for _ in range(M)]
book_id = [idx for idx in range(N)]

for _ in range(N):
    tmp = list(map(int, input().split(' ')))
    books.append(tmp)
    for idx in range(len(maximum)):
        maximum[idx] += tmp[idx+1]

for mx in maximum:
    if mx < X:
        print('-1')
        exit(0)

for book_num in range(1, N+1):
    combs = list(itertools.combinations(book_id, book_num))
    for comb in combs:
        ab = [0 for _ in range(M)]
        s = 0
        flag = True
        for el in comb:
            s += books[el][0]
            ab = [x + y for (x, y) in zip(ab, books[el][1:])]
        for el in ab:
            if el < X:
                flag = False
        if flag and s < ans:
            ans = s

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

costs = []

for i in range(2**n):
  temp_cost = 0
  skill = np.zeros(m)
  for j in range(n):
    if i&1<<j:
      temp_cost += CA[j][0]
      skill += np.array(CA[j][1:])
      
  if all(skill>=x):
    costs.append(temp_cost)
    
if costs:
  print(min(costs))
else:
  print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations


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

mtable = [None]*N
cs = []
for n in range(N):
    aa = list(map(int,input().split()))
    c = aa.pop(0)
    cs.append(c)
    ms = aa
    mtable[n] = ms
    

# print(mtable)
idxes = list(range(N))

prices = []
for i in range(1, N+1):
    for c in combinations(idxes, i):
        sums = [0]*M
        for idx in c:
            for i, m in enumerate(mtable[idx]):
                sums[i] += m
        if all(map(lambda x:x >= X, sums)):
            price = 0
            for idx in c:
                price += cs[idx]

            prices.append(price)
if prices == []:
    print(-1)
else:
    print(min(prices))

Submission status: Accepted

Solution code:
line1 = input().split()
n = int(line1[0])
m = int(line1[1])
x = int(line1[2])

books = []
for i in range(n):
  line = input().split()
  book = [int(line[0])]
  for j in range(1, m + 1):
    book.append(int(line[j]))
  books.append(book)

# 全件検索する
prices = []
for p in range(2 ** n):
  u = [0] * m
  p_str = format(p, 'b').zfill(n)
  price = 0
  for k in range(len(p_str)):
    if p_str[k] == '1':
      price += books[k][0]
      for j in range(m):
        u[j] += books[k][j + 1]
  if min(u) >= x:
    prices.append(price)

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