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:
from operator import add
n,m,x = map(int,input().split())
matrix = []
sum_list = [0 for i in range(m+1)]
for i in range(n):
    tmp = list(map(int,input().split()))
    matrix.append(tmp)
def tansaku(l,s):
    #一番前の参考書を入れる入れないで再起して、入れる参考書で得られるリストを返す、もうなければ全部が閾値を超えてるかを判断して超えてれば
    if len(l) == 0:
        if min(s[1:]) >= x:
            return s[0]
        else:
            return 10 ** 8
    else:
        tmp1 = tansaku(l[1:],s)
        s = list(map(add,s,l[0]))
        tmp2 = tansaku(l[1:],s)
        return min(tmp1,tmp2)
ans = tansaku(matrix,sum_list)
if ans == 10**8:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import copy
import itertools
import sys

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

us = [0 for _ in range(m)]

l = []
for i in range(n):
    row = [int(i) for i in input().split()]
    l.append(copy.deepcopy(row))

# 最初の一つをx以上にする組み合わせ
first = []
c = 0
for i in range(1, n+1):
    c = itertools.combinations(range(n), i)
    for v in c:
        total = 0
        for e in v:
            total += l[e][1]
        if total >= x:
            first.append(v)

for i in range(2, m+1):
    cc = copy.deepcopy(first)
    first = []
    for v in cc:
        total = 0
        for e in v:
            total += l[e][i]
        if total >= x:
            first.append(v)

if len(first) == 0:
    print(-1)
    sys.exit()

ans = (100000*n)+1
for i in first:
    t = 0
    for j in i:
        t += l[j][0]
    if ans > t:
        ans = t

print(ans)

Submission status: Accepted

Solution code:
from itertools import compress, product

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

for p in product(range(2), repeat=N):
    sumlist = [0] * (M+1) 
    for c in compress(clist, p):
        for i, val in enumerate(c):
            sumlist[i] += val
    if all(i >= X for i in sumlist[1:]):
        prices.append(sumlist[0])

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

Submission status: Accepted

Solution code:
import itertools

books = {}
name = 1
N,M,X = map(int, input().split())
for i in range(N):
    book = [int(i) for i in input().split()]
    books[name] = book
    name += 1

choices = []
for i in range(len(books.keys())):
    for j in itertools.combinations(books.keys(), i+1):
        choices.append(j)

prizes = []
for choice in choices:
    # print(choice)
    prize = 0
    score = [0]*M
    for num in choice:
        prize += books[num][0]
        score = [score[i]+books[num][i+1] for i in range(0,len(score))]
    # print(score)
    # print(min(score))
    # print(prize)
    if X<=min(score): 
        prizes.append(prize)
    # print('----')
if len(prizes) != 0: print(min(prizes))
else: print('-1')

Submission status: Accepted

Solution code:
import numpy as np
from functools import reduce
import math

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

books = []
moneys = []
for i in range(N):
    C = list(map(int, input().split()))
    moneys.append(C[0])
    books.append(np.array(C[1:]))
moneys = np.array(moneys)
books = np.array(books)

coms = [np.array(list(map(int, bin(i)[2:].rjust(N, "0")))) for i in range(2**N)]

min_val = math.inf
for com in coms[1:]:
    if sum([X]*M <= reduce(lambda a, b: a+b, books[com==1])) == M:
        min_val = min(min_val, sum(moneys[com==1]))
        
if min_val == math.inf:
    print(-1)
else:
    print(min_val)

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int,  input().split())
c=[]
a=[]
for _ in range(n):
    y = list(map(int, input().split()))
    c.append(y[0])
    a.append(y[1:])
    
def dfs(i, sum_c, sum_a):
    if i==n:
        if sum(sum_a>=x) == m:
            return sum_c
        else:
            return 10**12
    s1=dfs(i+1, sum_c+c[i], sum_a+np.array(a[i]))
    s2=dfs(i+1, sum_c, sum_a)
    return min(s1, s2)
  
ans=dfs(0, 0, np.array([0]*m))
if ans==10**12:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

I = []

for i in range(n):
  I.append(list(map(int, input().split())))
    
ans = 10000000000000
  
for i in range(1<<n):
  u = [0] * m
  c = 0
  for j in range(n):
    if (i>>j) % 2 == 1:
      for k in range(m):
        u[k] += I[j][k+1]
      c += I[j][0]
        
  flag = 1
  for e in u:
    if e < x:
      flag = 0
      
  if min(u) < x:
    continue
  else:
    ans = min(ans, c)

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

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N,M,X=map(int,input().split())
a=[]
b=[]
seq=[]

for i in range(0,N):
    seq.append(i)
for _ in range(0,N):
    a.append(list(map(int,input().split())))
a=np.array(a)
ans=10**7+1
for j in range(1,N+1):
    alist=list(itertools.combinations(seq,j))
    for k in range(len(alist)):
        b=list(alist[k])
        c=sum(a[b])
        if min(c[1:])>=X:
            ans=min(ans,c[0])
if ans==10**7+1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools

def main(N, M, X, CA):
    cand = []
    for n in range(N):  # n個選ぶ
        for ca in itertools.combinations(CA, n+1):
            s, price = f(ca)
            if all(i >= X for i in s):
                cand.append(price)
    if len(cand) == 0:
        print(-1)
    else:
        print(min(cand))


def f(lst):
    s = [0 for _ in range(M)]
    price = 0
    for ca in lst:
        price += ca[0]
        for i in range(M):
            s[i] += ca[i+1]
    return s, price





if __name__ == '__main__':
    N, M, X = list(map(int, input().split()))
    CA = []
    for _ in range(N):
        CA.append(list(map(int, input().split())))

    main(N, M, X, CA)

Submission status: Accepted

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
n, m, x = map(int, input().split())
cs = [0] * n
As = [[0] * m] * n

for i in range(n):
    cs[i], *As[i] = list(map(int, input().split()))

ans = 10 ** 8  # 十分に大きい初期値

for i in range(2 ** n):
    # 初期値
    amount = 0
    probs = [0] * m
    flags = bin(i)[2:].zfill(n)

    for j in range(n):
        c = cs[j]
        val = int(flags[j])
        amount += val * c
        for k in range(m):
            probs[k] += val * As[j][k]

    if (len(list(filter(lambda p: p < x, probs))) == 0):
        ans = min(ans, amount)


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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
ANS=[]
now=[0]*(M+1)
i=0
j=0
def choice(now,A,i,N,ANS):
    if i==N-1:
        add=[x+y for (x,y) in zip(now,A[i])]
        ANS.append(now)
        ANS.append(add)
    else:
        add=[x+y for (x,y) in zip(now,A[i])]
        choice(now,A,i+1,N,ANS)
        choice(add,A,i+1,N,ANS)

choice(now,A,i,N,ANS)
ans=1200001
for i in range(len(ANS)):
    for j in range(1,M+1):
        if ANS[i][j]<X:
            break
    else:
        ans=min(ans,ANS[i][0])
if ans==1200001:
    ans=-1
print(ans)

Submission status: Accepted

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

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

goal = [x] * (m)

def infer(ans):
    for i in range(m):
        if goal[i] > ans[i]:
            return False
    return True

cost = 10 ** 12
flag = False
for i in range(2**n):
    bag = [0] * (m)
    total = 0
    for j in range(n):  
        if ((i >> j) & 1):
            bag = [bag[k] + a[j][k] for k in range(m)]
            total += c[j]
    
    if infer(bag):
        cost = min(cost, total)
        flag = True
print(cost if flag else -1)

Submission status: Accepted

Solution code:
import itertools
import sys
import numpy as np

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

result = []
for n in range(2 ** N):
    ii = [0] * N
    for i in range(N):
        if (n >> i) & 1:
            ii[i] = 1
    # print(ii)
    tmp = [0] * (M + 1)
    for j in range(len(ii)):
        if ii[j] == 1:
            tmp = (np.array(tmp) + np.array(C[j])).tolist()
    result.append(tmp)


def ex(array):
    for i in array[1:]:
        if i < X:
            return False
    return True


min_value = sys.maxsize
result.sort()
for r in result:
    if ex(r):
        print(r[0])
        exit()

print(-1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import product

N,M,X = LI()
C = [0]*N
A = []
for i in range(N):
    x = LI()
    C[i] = x[0]
    A.append(x[1:])

Z = list(product([False,True],repeat=N))
ans = float('inf')
for z in Z:
    cost = 0
    rikai = [0]*M
    for i in range(len(z)):
        if z[i]:
            cost += C[i]
            for j in range(M):
                rikai[j] += A[i][j]
    flag = False
    for i in range(M):
        if rikai[i] < X:
            flag = True
            break
    if not flag:
        if cost < ans:
            ans = cost

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

Submission status: Accepted

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

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

for cnt in range(2**n):
    aa=[0 for j in range(m)]
    mon=0
    for i in range(n):
        if 2**i & cnt !=0:
            mon+=c[i]
            for mm in range(m):
                aa[mm]+=a[i][mm]
    if min(aa) >= x:
        ok = True
        money.append(mon)

if ok:
    print(min(money))
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np
import sys

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

Cs = []

for _ in range(N):
    Cs.append(list(map(int,(input().split()))))

Cs = np.array(Cs)

patterns = product([0, 1], repeat=N)

ans = 10**12

for pattern in patterns:
    # print(pattern)
    for i in range(len(pattern)):
        en = 0
        unds = np.array([0]*M)
        for p in range(len(pattern)):
            if pattern[p] == 1:
                unds += Cs[p, 1:]
                en += Cs[p][0]
                if all([u >= X for u in unds]):
                    # print('p', pattern)
                    ans = min(ans, en)

if ans == 10**12:
    print(-1)
    sys.exit()

# print('-----output-----')
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

List = []

Max = 10 ** 7

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

#print(List)
l = []
for i in range(N):
    l.append(i)

for i in range(N, 0, -1):
    for j in itertools.combinations(l, i):
        Sum = [0] * (M+1)
        flg = 0
        for k in j:
            for h in range(M+1):
                Sum[h] += List[k][h]
        #print(Sum)
        if Sum[0] <= Max:
            for a in range(1, M+1):
                if Sum[a] < X:
                    flg = 1
                    break
            if flg == 0:
                Max = Sum[0]

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

Submission status: Accepted

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

for i in range(n):
    lst.append([int(i) for i in input().split()])

ans_list = []

for i in range(1, n + 1):
    for j in itertools.combinations(lst, i):
        under_list = [0] * m
        money = 0
        for k in j:
            money += k[0]
            for i in range(m):
                under_list[i] += k[i + 1]
        if all([i >= x for i in under_list]):
            ans_list.append(money)

if not ans_list:
    ans = -1
else:
    ans = min(ans_list)

print(ans)

Submission status: Accepted

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

mi = 1 << 100
for i in range(1 << N):
    B = [0] * M
    c = 0
    for j in range(N):
        if i >> j & 1:
            a = A[j]
            c += C[j]
            for k in range(M):
                B[k] += a[k]
    if min(B) >= X:
        mi = min(mi, c)

print(mi if mi < 1 << 99 else -1)

Submission status: Accepted

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

for i in range(1, n+1):
    for vl in itertools.combinations(c, i):
        a = [0] * m
        p = 0
        for v in vl:
            p += v[0]
            for j in range(m):
                a[j] += v[1+j]
        flag = True
        for k in range(m):
            if a[k] < x:
                flag = False
        if flag:
            ans.append(p)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np
import itertools as iters

n, m , x = list(map(int, input().split()))
c = np.empty((n, 1))
a = np.empty((n, m))

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

max_score = sum(a)

if 1 in (max_score < x):
  print(-1)
  exit()

min_price = 10 ** 10

for i in range(n):
  pairs = iters.combinations(range(n), i+1)
  for pair in pairs:
    price = 0
    check = np.zeros((1, m))
    for idx in pair:
      price += c[idx]
      check += a[idx]
    if 1 not in (check < x):
      if price < min_price:
        min_price = price

print(int(min_price))

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N,M,X = map(int, input().split())		# 5 7 2
CA = [list(map(int, input().split())) for _ in range(N)]		#=> [[1, 0], [2, 10], [3, 210], [4, 3210]]

A=[]
C=[]
for n in range(N):
	A.append(CA[n][1:])
	C.append(CA[n][0])

B=[0]*M

for n in range(N):
	for m in range(M):
		B[m] += A[n][m]

#p(CA)
#p(A)
#p(C)
#p(B)

if min(B) < X:
	print(-1)
	exit(0)

# 直積 product
# デカルト積。for ループの入れ子をせずに全パターンを網羅するときに便利。
from itertools import product
L = list( product([0,1], repeat=N) )

#p(L)

from operator import add

ans = sum(C)
for l in L:
	sumA = [0]*M
	sumC = 0
	for i,x in enumerate(l):
		if x==0: continue
		sumA = map(add, sumA, A[i])
		sumC += C[i]
		
	if min(sumA) < X: continue
	
	ans = min(ans, sumC)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

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

op_cnt = n  # 本の数

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

ans = float('inf')
Flg = False
for i in range(2 ** op_cnt):
    money = 0
    A = [0] * m
    op = [True] * op_cnt  
    for j in range(op_cnt):
        if ((i >> j) & 1):
            op[op_cnt - 1 - j] = False  
    for j in range(n):#買う買わない
        if op[j]:
            money += C[j]
            for k in range(m):#買う場合の経験値上昇
                A[k] += L[j][k]
    flg = True
    #print(money,A)
    for a in A:
        if a < x:
            flg = False
    if flg:
        ans = min(ans,money)
        Flg = True

if Flg:
    print(ans)
else:
    print('-1')

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
sum=[0]*m
for i in range(n):
  for j in range(1,m+1):
    sum[j-1]+=l[i][j]
for ss in sum:
  if ss<x:
    print(-1)
    exit()
list=[]
for p in itertools.product([1,0],repeat=n):
  cnt=[0]*m
  ans=0
  for i in range(n):
    if p[i]==1:
      ans+=l[i][0]
      for j in range(1,m+1):
        cnt[j-1]+=l[i][j]
  if all(cc>=x for cc in cnt):
    list.append(ans)
print(min(list))

Submission status: Accepted

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

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

BASE = 1000000000000000
ans = BASE
def dfs(idx, num_list):
    global ans
    global c
    global a
    if idx == n:
        tmp_c_ans = 0
        tmp_a_ans = [0 for i in range(m)]
        for c_idx, c_include in enumerate(num_list):
            if c_include == 1:
                tmp_c_ans += c[c_idx]
                for a_idx, a_score in enumerate(a[c_idx]):
                    tmp_a_ans[a_idx] += a_score
        if all([t >= x for t in tmp_a_ans]):
            ans = min(ans, tmp_c_ans)
    else:
        dfs(idx + 1, num_list + [1])
        dfs(idx + 1, num_list + [0])

dfs(0, [])

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

Submission status: Accepted

Solution code:
import itertools

N,M,X = map(int, input().split())
books = list()
for _ in range(N): books.append(list(map(int, input().split())))

MAX_COST = 1e5*12+1
min_cost = MAX_COST
selector = [i for i in range(N)]
for n in range(1, len(selector)+1):
	for conb in itertools.combinations(selector,n):
		cost = 0
		rikai = [0 for _ in range(M)]
		for sel in conb:
			cost += books[sel][0]
			for i in range(M): rikai[i] += books[sel][i+1]
		if all(a >= X for a in rikai):
			if cost < min_cost: min_cost = cost

if min_cost != MAX_COST:
	print(min_cost)
else:
	print(-1)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

@lru_cache(None)
def recur(temp, index=0, cost=0):
    if index == n:
        for j in range(m):
            if temp[j] < x:
                return inf
        return cost
    answer = inf
    answer = min(answer, recur(temp, index+1, cost))
    temp = list(temp)
    for j in range(m):
        temp[j] += mat[index][j+1]
    cost += mat[index][0]
    answer = min(answer, recur(tuple(temp), index+1, cost))
    return answer


n, m, x = sp()
mat = []
for i in range(n):
    mat.append(l())
res = recur(tuple([0]*m))
if res == inf:
    out(-1)
    exit()
out(res)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
import copy
ans1 = 10**10
g = []
def v(a,b):
    for i in range(len(a)):
        a[i] += b[i]
    return a
b = [0 for i in range(n)]
for i in range(n):
    a = list(map(int,input().split()))
    g.append(a)
for i in range(len(g)):
    b[i] = g[i][0]
    g[i].pop(0)
for i in range(2**n):
    ans = 0
    ni = [0 for s in range(m)]
    u = copy.deepcopy(i)
    for j in range(n):
        if u &1 == 1:
            ni = v(ni,g[j])
            ans += b[j]
        u = u >> 1
    if min(ni) >= x:
        ans1 = min(ans1,ans)
if ans1 == 10**10:
    print(-1)
else:
    print(ans1)

Submission status: Accepted

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

def rec(r,progress,result):
    if r == N:
        result.append(progress)
        progress = progress + [grid[N]]
        result.append(progress)
        return
    else:
        rec(r+1,progress,result)
        progress = progress + [grid[r]]
        rec(r+1,progress,result)

def rap():
    result = []
    progress = []
    rec(0,progress,result)
    ans = float('inf')
    for item in result:
        stals = [0]*(M+1)
        for item2 in item:
            for i, j in enumerate(item2):
                stals[i] += j
        f = True
        for  m in stals[1:]:
            if m < X:
                f = False
        if f:
            ans = min(ans,stals[0])
    if  ans == float('inf'):
        print(-1)
    else:
        print(ans)
            
    return 

rap()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = []
a = [[] for _ in range(n)]
for i in range(n):
  inp = list(map(int, input().split()))
  c.append(inp[0])
  for j in range(m):
    a[i].append(inp[j+1])
kumi=1
for i in range(n):
  kumi *= 2
  
min_score = 10000000000000
for i in range(1, kumi):
  t = [0 for _ in range(m)]
  p = 0
  ni = format(i, 'b').zfill(n)
  for j in range(n):
    if(ni[j]=="1"):
      for kk in range(m):
        t[kk] += a[j][kk]
      p += c[j]
  flag = True
  for j in range(m):
    if(t[j] < x):
      flag = False
  if(flag):
    if(min_score > p):
      min_score = p
      
if(min_score == 10000000000000):
  print(-1)
else:
  print(min_score)

Submission status: Accepted

Solution code:
import itertools
 
N,M,X = map(int, input().split())
C_A = []
for _ in range(N):
    C_A.append(list(map(int, input().split())))
# print(C_A)
 
min_price = 10**5 * 12 
rikaido = [0 for _ in range(M)]
possible = 0
for i in itertools.product([0,1], repeat=N):
    price_rikaido = [sum(C_A[j][k]*i[j] for j in range(N)) for k in range(M+1)]
    # print(i)
    # print(price_rikaido)
    flag = 1
    for l in range(M):
        if price_rikaido[l+1] <X:
            flag = 0
            break
    if flag and (min_price >= price_rikaido[0]):
        min_price = price_rikaido[0]
        possible = 1
        
if possible:
    print(min_price)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools

def check(arr,t):
    for i in arr:
        if i < t:
            return False
    return True

N,M,X = list(map(int,input().split()))
l = []
for _ in range(N):
    l.append(list(map(int,input().split())))
buy_bit = list(itertools.product([0,1], repeat=N))

mi = 990000000
for pattern in buy_bit:
    learned = [0 for _ in range(M)]
    total = 0
    for idx,bit in enumerate(pattern):
        if bit == 1:
            total += l[idx][0]
            for learned_id in range(M):
                learned[learned_id] += l[idx][learned_id+1]
    if total < mi and check(learned,X):
        mi = total
if mi == 990000000:
    print(-1)
else:
    print(mi)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

n, m, x = map(int, input().split())
c = []
a = []
for i in range(n):
    cu, *au = list(map(int, input().split()))
    c.append(cu)
    a.append(au)
c = np.array(c)
a = np.array(a)
    
pmin = 10000000
for e in itertools.product([0, 1], repeat=n):
    e = np.array(e)
    results = np.dot(e, a)
    if results.min()>=x:
        p = np.dot(e, c)
        if p < pmin:
            pmin = p

pmin = -1 if pmin==10000000 else pmin
print(pmin)

Submission status: Accepted

Solution code:
from itertools import combinations
n, m, x = map(int, input().split())

books = []

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

combBooks = []
for i in range(n, 0, -1):
    combBooks.append(list(combinations(books, i)))
prices = []
flag = True
for combin in combBooks:
    if flag:
        flag = False
        for comb in combin:
            sums = [0]*m
            price = 0
            for book in comb:
                price += book[0]
                for algorithm in range(m):
                    sums[algorithm] += book[algorithm+1]
            flag_break = True
            for sum in sums:
                if sum < x:
                    flag_break = False
                    break
            if flag_break:
                flag = True
                prices.append(price)

if not prices:
    print("-1")
else:
    print(min(prices))

Submission status: Accepted

Solution code:
import itertools

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


kakaku = 9999999
combinations = []
for n in range(1, N+1):
    combinations += list(itertools.combinations(range(N), n))

for pair in combinations:
    hantei = True
    for m in range(M):
        total = 0
        for i in pair:
            total += CA[i][m+1]
        if X <= total:
            continue
        else:
            hantei = False
            break
    if hantei:
        kingaku = 0
        for i in pair:
            kingaku += CA[i][0]
        kakaku = min(kakaku, kingaku)
    else:
        continue

if kakaku == 9999999:
    print(-1)
else:
    print(kakaku)

Submission status: Accepted

Solution code:
import numpy as np 


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


s_list = list()

for i in range(n):
    line = list(map(int, input().split()))
    s_list.append([line[0], np.array(line[1:], dtype=int)])


cands = list()
# cost, value
cands.append([0, np.zeros(m, dtype=int)])


for l in s_list:
    next_cands = list()
    for c in cands:
        next_cands.append([c[0] + l[0], c[1] + l[1]])
    cands += next_cands


min_cost = 10**12
for l in cands:
    if (l[1] >= x).all() and l[0] < min_cost:
        min_cost = l[0]


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

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
c=[None for i in range(n)]
a=[None for i in range(n)]
for i in range(n):
    l=[int(i) for i in input().split()]
    c[i]=l[0]
    a[i]=np.array(l[1:])
mincos=1000000000000
for mask in range(2**n):
    rikai=np.zeros(m,dtype="int32")
    cos=0
    mm=mask
    for i in range(n):
        if mm%2:
            rikai+=a[i]
            cos+=c[i]
        mm//=2
    if np.all(rikai>=x):
        mincos=min(cos,mincos)

if mincos==1000000000000:
    print(-1)
else:
    print(mincos)

Submission status: Accepted

Solution code:
def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

# 学びたいアルゴリズムの数 M
# 参考書の数 N
# i番目の参考書はC_i円
# j番目のアルゴリズムの理解度がA_i,j上昇
# 理解度の目標値 X
# -> 全てをX以上にしたい
# 可能な場合金額の最小値、不可能な場合 -1

N, M, X = mapint_inp()
CA = [list(mapint_inp()) for _ in range(N)]

total_value_and_understanding_value = []

def add_each_element_in_list(l1, l2):
    return [a + b for a, b in zip(l1, l2)]


totals = []
for i in range(2**N):
    t = []
    for j in range(N):
        if ((i >> j) & 1):
            if t:
                t = add_each_element_in_list(t, CA[j])
                continue
            t = CA[j]
    if t:
        totals.append(t)

def check_X(l):
    for i in range(M+1):
        if i == 0:
            continue
        if l[i] < X:
            return False
    return True

import math
ans = math.inf
f = False
for total in totals:
    if check_X(total):
        ans = min(total[0], ans)

if ans == math.inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    IN1 = [int(_) for _ in input().split()]
    N = IN1[0]
    M = IN1[1]
    X = IN1[2]
    AC = [[int(_) for _ in input().split()] for i in range(N)]

    minSum = 1200001
    for i in range(2 ** N):
        tmpSum = 0
        tmpA = [0] * M
        for j in range(N):
            if ((i >> j) & 1):
                tmpSum = tmpSum + AC[j][0]
                for k in range(1, M + 1):
                    tmpA[k-1] = tmpA[k-1] + AC[j][k]

        result = True
        for a in tmpA:
            if a < X:
                result = False
        if result:
            if minSum >= tmpSum:
                minSum = tmpSum

    if minSum != 1200001:
        print(minSum)
        return
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

bo =  []
for i in range(n):
    bo.append([int(j) for j in input().split()])
# bo = [int(i) for i in [j for j in sbo] ]

cost = 999999999999
pat = []
for i in range(2 ** n):
    tp = []
    for j in  range(n):
        if ((i >> j) & 1):
            tp.append(bo[j])
    pat.append(tp)

# print(pat)

for i in pat:
    ef = [0] * (m)
    tcost = 0
    for j in i:
        tcost += j[0]
        for k in range(1,m+1):
            ef[k-1] += j[k]
    flg = True
    for l in range(1,m+1):
        if ef[l-1] < x:
            flg = False
    if flg:
        cost = min(cost,tcost)

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

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
l=list()
for i in range(n):
    l.append(list(map(int,input().split())))
pp=list()
for i in range(1,n+1):
    for j in itertools.combinations(l,i):
        r=[0 for i in range(m)]
        for k in j:
            a=0
            p=0
            for i in range(1,m+1):
                r[i-1]+=k[i]
                a+=r[i-1]>=x
            if a==m:
                for c in j:
                    p+=c[0]
                pp.append(p)
if len(pp)==0:
    print(-1)
else:
    print(min(pp))

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
#S= str(input())
#T= str(input())
N,M,X = map(int,input().split())
#N = int(input())
#A = list(map(int,input().split()))
a=[]
ans=[]
for j in range(N):

    A = list(map(int,input().split()))
    a.append(A)

for i in range(1,N+1):
    for l in list(combinations(a,i)):
        s=np.zeros(M+1)
        for k in l:
            k=np.array(k)
            s=s+k
        #print(s)

        if min(s[1:])>=X:
            ans.append(s[0])
if len(ans)==0:
    print(-1)
else:
    print(int(min(ans)))