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:
#code 
#c
n,m,x=map(int,input().split())
from itertools import combinations
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
l1=[]
for i in range(n):
    l1.append(i)
l2=[]
for i in range(1,n+1):
    lx=[0]*i
    lyy=[0]*m
    for lx in combinations(l1,i):
        ly=lyy.copy()
        a=0
        for p in range(1,m+1):
            for k in lx:
                ly[p-1]+=l[k][p]
        for k in lx:
            a+=l[k][0]
        for j in ly:
            if j<x:
                a=0
                break
        if a!=0:
            l2.append(a)
if len(l2)!=0:
    print(min(l2))
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import deque

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

row = [i for i in range(1, N+1)]
ans = float("INF")
for i in range(1, N+1):
  for v in combinations(row, i):
    q = deque(v)
    cost = 0
    Asum = [0]*M
    while q:
      a = q.popleft() - 1
      cost += CA[a][0]
      for j in range(M):
        Asum[j] += CA[a][j+1]
    flag = True
    for m in range(M):
      if Asum[m] < X:
        flag = False
    if flag:
      ans = min(ans, cost)
if ans == float("INF"):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
def count_score(v):
    score = [0] * m
    for j in range(m):
        t = 0
        for i in range(n):
            t += a[i][j] * v[i]
        score[j] = t
    return score


def count_money(v):
    money = 0
    for i in range(n):
        money += c[i] * v[i]
    return money


def judge_understanding(score):
    ans = True
    for j in range(m):
        if score[j] < x:
            ans = False
            break
    return ans


def pu(j, in_vec, max_money):
    if j == n - 1:
        vec0 = in_vec
        vec0[n - 1] = 0
        score0 = count_score(vec0)
        money0 = count_money(vec0)
        understanding0 = judge_understanding(score0)

        vec1 = in_vec
        vec1[n - 1] = 1
        score1 = count_score(vec1)
        money1 = count_money(vec1)
        understanding1 = judge_understanding(score1)

        if understanding0:
            ans_vec = vec0
            ans_money = money0
        elif understanding1:
            ans_vec = vec1
            ans_money = money1
        else:
            ans_vec = in_vec
            ans_money = max_money
        
        return ans_vec, ans_money

    else:
        vec0 = in_vec
        vec0[j] = 0
        ans_vec0, ans_money0 = pu(j + 1, vec0, max_money)
        
        vec1 = in_vec
        vec1[j] = 1
        ans_vec1, ans_money1 = pu(j + 1, vec1, max_money)

        if ans_money0 <= ans_money1:
            ans_money = ans_money0
            ans_vec = ans_vec0
        else:
            ans_money = ans_money1
            ans_vec = ans_vec1

        return ans_vec, ans_money


if __name__ == "__main__":
    n, m, x = map(int, input().split())    
    c = [0] * n
    a = [[0] * m] * n

    for i in range(n):
        l = [int(x) for x in input().split()]
        c[i] = l[0]
        a[i] = l[1:m + 1]


    v = [0] * n

    mm = 1
    for i in range(n):
        mm += c[i]

    ans_vec, ans_money = pu(0, v, mm)

    if mm == ans_money:
        print(-1)
    else:
        print(ans_money)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

num = [i for i in range(n)]

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


correct = []
for k in range(1, n+1):

  for v in itertools.combinations(num, k):
    test = [] #組み合わせを作る
    for j in v:
      test.append(book_list[j])
      sum_test = np.sum(test, axis = 0) #組みあわせの合計
      cnt = 0
      for i in range(1, m+1):
        if sum_test[i] >= x:
          cnt += 1
      if cnt == m:
        correct.append(sum_test[0]) #正解を入れる
        
if sum(correct) > 0:
  print(min(correct))
    
else:
  print('-1')

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m, x = map(int, input().split())
c_list = []
a_list = []
for i in range(0, n):
    y_list = list(map(int, input().split()))
    c_list.append(y_list[0])
    a_list.append(y_list[1:])
ans = []
for i in range(0, 2**n):
    cost = 0
    gaku = [0] * m
    for j in range(0, n):
        if ((i >> j) & 1):
            cost += c_list[j]
            for k in range(0, m):
                gaku[k] += a_list[j][k]
    if all([r >= x for r in gaku]):
        ans.append(cost)
if ans:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

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


import itertools
M = 100000000000
ans = 0

for i in itertools.product([0, 1], repeat=n):
    dp = [0]*m
    tm= 0 
    for I in range(n):
        if i[I] == 1:
            for j in range(m):
                dp[j] += L[I][j]
            tm += C[I]* i[I]
    if all(dp[t]>=x for t in range(m)):
        M = min(M,tm)
if M==100000000000:
    print(-1)
else:
    print(M)

Submission status: Accepted

Solution code:
def resolve():
    import itertools
    impossible = 10 ** 20
    n, m, x = map(int, input().split())
    ans = impossible
    books = [None] * n
    for i in range(n):
        books[i] = list(map(int, input().split()))
    for i in itertools.product([True, False], repeat=n):
        u = [0] * m
        yen = 0
        for index, j in enumerate(i):
            if not j:
                continue
            yen += books[index][0]
            for k in range(m):
                u[k] += books[index][k + 1]
        for j in u:
            if j < x:
                break
        else:
            ans = min(yen, ans)
    print(ans if ans < impossible else -1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

cost = 100000000000000000000000
l = list(range(1,N+1))
import itertools
for i in range(1,N+1):
    check_l = list(itertools.combinations(l,i))
    for a in check_l:
        sub_list = [0] * (M + 1)
        for j in range(i):
            for k in range(M+1):
                sub_list[k] += C[a[j]-1][k]
        flag = True
        for p in range(M):
            if sub_list[p+1] < X:
                flag = False
        if flag == True:
            if cost > sub_list[0]:
                cost = sub_list[0]

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

Submission status: Accepted

Solution code:
import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict
from itertools import combinations as cmb

def check(s: list):
    if min(s) < X:
        return False
    return True

N, M, X = map(int, input().split())
G = [tuple(map(int, input().split())) for _ in range(N)]
s = [0 for i in range(M)]

res = 10 ** 15
ok = False
for i in range(1, N + 1):
    for cm in cmb(range(0, N), i):
        cnt = 0
        s = [0 for i in range(M)]
        for c in cm:
            cnt += G[c][0]
            for j in range(M):
                s[j] += G[c][j + 1]
        if check(s):
            res = min(cnt, res)
            ok = True

if ok:
    print(res)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
from itertools import combinations
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
l1=[]
for i in range(n):
    l1.append(i)
l2=[]
for i in range(1,n+1):
    lx=[0]*i
    lyy=[0]*m
    for lx in combinations(l1,i):
        ly=lyy.copy()
        a=0
        for p in range(1,m+1):
            for k in lx:
                ly[p-1]+=l[k][p]
        for k in lx:
            a+=l[k][0]
        for j in ly:
            if j<x:
                a=0
                break
        if a!=0:
            l2.append(a)
if len(l2)!=0:
    print(min(l2))
else:
    print(-1)

Submission status: Accepted

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

cmin = 10**8
csum = 0
asum = [0 for i in range(m)]
for i in range(2**n):
    csum = 0
    for k in range(m):
        asum[k] = 0
    for j in range(n):
        if (i>>j)&1:
            csum+=c[j]
            for k in range(m):
                asum[k] += a[j][k]
    b = True
    for k in range(m):
        if asum[k]<x:
            b = False
            break
    if b:
        cmin = min(cmin,csum)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(" "))
B_list = []


for Books in range(N):
    B_list.append(list(map(int, input().split(" "))))
# print(B_list)

bug = []
for k in range(M + 1):
    bug.append(0)
# print(bug)
ways = []

for way in range(2**N):
    for book in range(N):
        if ((way >> book) & 1) == 1:
            for i in range(M + 1):
                bug[i] += B_list[book][i]

    # print(bug)
    O = bug.pop(0)
    clear = [l for l in bug if l >= X]
    # print(clear)

    if len(bug) == len(clear):
        ways.append(O)

    bug = []
    for k in range(M + 1):
        bug.append(0)

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

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
num = []
for i in range(n):
    tmp = list(map(int, input().split()))
    num.append(tmp)

res = []
for i in range(1, len(num)+1):
    for conb in itertools.combinations(num, i):
        res.append(list(conb))
mini = float('inf')
for i in range(len(res)):
    tmp2 = [0] * (m+1)
    f = True
    for j in range(len(res[i])):
        for k in range(m+1):
            tmp2[k] += res[i][j][k]
    
    for l in range(len(tmp2)-1):
        if tmp2[l+1] < x:
            f = False
    if f == True and mini > tmp2[0]:
        mini = tmp2[0]

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

Submission status: Accepted

Solution code:
n, m, X = map(int, input().split())
 
ans = 10**9
 
price = []
a = []
for _ in range(n):
    c = [int(x) for x in input().split()]
    price.append(c[0])
    a.append(c[1:])
 
for i in range(1 << n):
    l = [0]*m
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            tmp += price[j]
            for x in range(m):
                l[x] += a[j][x]
    if all(x >= X for x in l):
        ans = min(ans, tmp)
 
print(-1 if ans == 10**9 else ans)

Submission status: Accepted

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

INF = float('INF')
min_cost = INF


def dfs(i, cost, learn):
    if i == N:
        if min(learn) >= X:
            return cost
        else:
            return INF
    else:
        new_learn = [x + y for (x, y) in zip(A[i], learn)]
        cost = min(dfs(i + 1, cost, learn), dfs(i + 1, cost + C[i], new_learn))
        return cost


min_cost = dfs(0, 0, [0] * M)

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

Submission status: Accepted

Solution code:
n, m, x = map(int,input().split())
li = [[] for i in range(n)]
minm = 10000000
argl = [0] * m
for i in range(n):
    li[i] = list(map(int,input().split()))

def a(item, money, arg):
    if item == n:
        return 10000000

    nobuy = a(item + 1, money, arg)
    # buy
    newarg = arg.copy()
    for i in range(m):
        newarg[i] += li[item][i + 1]
    
    flg = True
    for i in range(m):
        if newarg[i] < x:
            flg = False
    if flg:
        buy = money + li[item][0]
    else:
        buy = a(item + 1, money + li[item][0], newarg)
    
    return min(buy, nobuy)

res = a(0, 0, argl)
if res == 10000000:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
import sys
import numpy as np

def ls_add(l0,l1):
	return [l0[i] + l1[i] for i in range(len(l0))]

n,m,x = [int(e) for e in input().split(" ")[:3]]

book_ls = []
for i in range(n):
	inp_ls = [int(e) for e in input().split(" ")[:m+1]]
	# c, a_ls = inp_ls[0], inp_ls[1:]
	book_ls.append(inp_ls)

book_np_ls = np.array(book_ls)
all_sum = np.sum(book_np_ls, axis = 0)
all_result = np.count_nonzero(all_sum[1:] < x)

# 高橋くんが目標を達成できない
if all_result > 0:
	print("-1")
	sys.exit()

sum_dic = {tuple([i]): book_ls[i] for i in range(n)}
for i in range(1,n):
	key_ls = [e for e in list(sum_dic) if len(e) == i]
	for e in key_ls:
		ls0 = sum_dic[e]
		max_e = e[-1]
		for ee in range(max_e+1,n):
			ls1 = sum_dic[tuple([ee])]
			temp_ls = ls_add(ls0, ls1)
			sum_dic[tuple(list(e) + [ee])] = temp_ls

min_val = all_sum[0]
for key in sum_dic:
	temp_ls = sum_dic[key]
	flag_ls = [int(e < x) for e in temp_ls[1:]]
	if sum(flag_ls) != 0: continue
	if temp_ls[0] < min_val: min_val = temp_ls[0]

print(min_val)

Submission status: Accepted

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

b = [i for i in range(N)]
n = len(b)

b_pairs = []
for i in range(1, n+1):
    b_pairs += list(itertools.combinations(b, i))

cnt = 0
A = [0] * M
B = []
C = []
for i in range(2 ** N - 1):
  w = len(b_pairs[i])
  for j in range(M):
    for k in range(w):
      A[j] += l[b_pairs[i][k]][j + 1]
  B.append(A)
  A = [0] * M
  
for i in range(2 ** N - 1):
  w = len(b_pairs[i])
  for k in range(w):
    cnt += l[b_pairs[i][k]][0]
  C.append(cnt)
  cnt = 0

for i in range(len(B)):
  for j in range(M):
    if B[i][j] >= X:
      pass
    else:
      B[i] = 0
      break
if B == [0] * len(B):
  print(-1)
  exit()

for i in range(len(B)):
  if B[i] != 0:
    B[i] = C[i]
  else:
    B[i] = 1000000000000

print(min(B))

Submission status: Accepted

Solution code:

i = list(map(int, input().split()))
numBook  = i[0]
numTopic = i[1]
minKnow = i[2]
i=0
j=0 

Mat = [list(map(int, input().split()))  for i in range(numBook)]
#print(Mat)

#可能判定
for i in range(1,numTopic+1)	:
	knowledge = 0
	cost_out = 0
	for j in range(0,numBook)	:
		knowledge += Mat[j][i] 
		cost_out += Mat[j][0]
	if knowledge < minKnow	:
		print("-1")
		exit()	

#print("max cost is ",cost_out)
#価格策定
#print(2**numBook,"pattern")
for i in range(0,2**numBook)  :
	bin_str = format(i, '012b')
#	print("challenge with ",bin_str)
	#print(bin_str,"=>",bin_str[11])
	for i in range(1,numTopic+1)	:
		knowledge = 0
		cost = 0
		for j in range(0,numBook)	:
			knowledge += Mat[j][i] *int(bin_str[11-j])
			cost += Mat[j][0] * int(bin_str[11-j])
#		print("for topic", i, "this challenge gave knowledge of ", knowledge)
		if knowledge < minKnow	:
#			print("which is not enough.")
			break
	#print("this time it got ",cost)
	if cost != 0 	:
		if j == numBook-1 :
			if knowledge >= minKnow	:
				if cost < cost_out:
					cost_out = cost
					#print("with", bin_str)
print(cost_out)

Submission status: Accepted

Solution code:
from itertools import combinations
from sys import maxsize

def check(ls, x):
    for i in ls:
        if i < x:
            return False
    return True


n, m, x = map(int, input().split())
ls = []
a = [i for i in range(n)]
for i in range(n):
    ls.append(list(map(int, input().split())))
total_cost = maxsize
for i in range(1, n + 1):
    comb = list(combinations(a, i))
    for j in comb:
        mo = [0 for p in range(m)]
        cost = 0
        for k in j:
            cost += ls[k][0]
            for h in range(m):
                mo[h] += ls[k][h + 1]
        if check(mo, x):
            total_cost = min(total_cost, cost)

if total_cost ==maxsize:
    print(-1)
else:
    print(total_cost)

Submission status: Accepted

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

z = [i for i in range(1, N+1)]
m = [1000000000000000000]

for i in range(N):
    x = list(itertools.combinations(z,i+1))

    for s in x:

        for k in range(1,M+1):
            C = sum(A[j-1][k] for j in s)
            if C < X:
                break
        else:
            m.append(sum(A[o-1][0] for o in s))

print(min(m) if min(m)!=1000000000000000000 else -1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M,X=map(int,input().split())
lista=[]
for i in range(N):
    lista.append(list(map(int,input().split())))
lista=np.array(lista)
cost=1000000000000000
judge=[X]*M
data=[k for k in range(1,N+1)]
for i in range(1,N+1):
    a=list(itertools.combinations(data,i))
    for j in a:
        clist=np.array([0]*(M+1))
        for k in j:
            clist=clist+lista[k-1]
        if all(clist[1:]>=judge):
            if clist[0]<cost:
                cost=clist[0]
                m=j
c=0
try:
    for i in m:
        c+=lista[i-1][0]

    print(c)
except:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = list()
a = list()
for i in range(n):
  row_input = list(map(int, input().split()))
  c.append(row_input[0])
  a.append(row_input[1:])
inf_value = 2*sum(c)
def choose_next_row(partial_choice):
  if len(partial_choice) == n:
    if all(sum(partial_choice[i]*a[i][j] for i in range(n))>=x for j in range(m)):
      return sum(include*cost for include, cost in zip(partial_choice, c))
    else:
      return inf_value
  return min(choose_next_row(partial_choice+[0]), choose_next_row(partial_choice+[1]))
ans = choose_next_row([])
if ans == inf_value:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import numpy as np
# スペース区切りの整数入力
N,M,X = map(int, input().split())

a = np.zeros((N,M+1))

for i in range(N):
    # スペース区切りの整数をリストに入力
    a[i] = [int(x) for x in input().split()]

b = np.zeros(N)
c = np.zeros(M+1)
min_cost = 9999999999999999

for i in range(2**N):
    ii = i
    for j in range(N):
        b[j] = ii % 2
        ii = ii // 2
    c = np.zeros(M+1)
    flg = "ok"
    for k in range(M+1):
        for j in range(N):
            c[k] += a[j,k] * b[j]
        if k > 0 and c[k] < X:
            flg = "ng"
            continue
    if flg == "ok":
        min_cost = min(min_cost,c[0])

if min_cost == 9999999999999999:
    print(-1)
else:
    print(int(min_cost))

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
c=[]
a=[]
ans=float("inf")

for i in range(n):
    tmp=list(map(int,input().split()))
    c.append(tmp[0])
    a.append(tmp[1:])
for i in itertools.product([0,1],repeat=n):
    understand=[0]*m
    tmp=0
    for t,j in enumerate(i):
        if j==1:
            for u,k in enumerate(a[t]):
                understand[u]+=k
            tmp+=c[t]
    if ans>tmp and min(understand)>=x:
        ans=tmp
print(ans) if ans != float("inf") else print(-1)

Submission status: Accepted

Solution code:
import itertools
import sys

n, m, x = map(int, input().split())
num = list(list(map(int, input().split())) for i in range(n))

s = [i for i in range(n)]
t = []
list_num = []

for i in range(n):
  t.append(list(map(list, itertools.combinations(s, i + 1))))


for i in t:
  for j in i:
    k = [0] * (m + 1)
    for z in j:
      k = tuple(x + y for (x,y) in zip(k, num[z]))
    list_num.append(k)


list_num = list(sorted(list_num, key =lambda w : w[0]))
q = []

flag2 = 0

for i in list_num:
  flag = 1
  for j in range(1, m + 1):
    if(i[j] < x):
      flag = 0
  if(flag == 1):
    q.append(i[0])
    flag2 = 1

if(flag2 == 1):
  print(min(q))
else: 
  print(-1)

Submission status: Accepted

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

import itertools

N, M ,X  =  [int(i) for i in input().split()]
Cs = []
for i in range(N):
    Cs.append([int(i) for i in input().split()])


min_a = 10000000000000

for i in range(1, N+1):
    for team in itertools.combinations(Cs, i):
        money = [0] * (M+1)
        for t in team:
            money = [i+j for i,j in zip(money,t)]
        flag = 1
        for m in money[1:]:
            if m < X:
                flag = 0
        if flag == 1 and min_a > money[0]:
            min_a = money[0]
if min_a == 10000000000000:
    print(-1)
else:
    print(min_a)

Submission status: Accepted

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

for i in range(2 ** n):
    tmp_price = 0
    lst = [0] * (m + 1)
    for j in range(n):
        if((i >> j) & 1):
            lst = [z + y for (z, y) in zip(lst, ca[j])]
    a = lst[1:]

    if all(t >= x for t in a):
        tmp_price = lst[0]
        price = min(tmp_price, price)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, m, x = list(map(int, input().split()))
lis = [list(map(int, input().split())) for i in range(n)]
ans = float('inf')
ima = [0]*m
def solve(i,ima,sum):
  newima=[0]*m
  #print("i: "+str(i))
  #print("ima")
  #print(ima)
  #print("sum: "+str(sum))
  global ans
  mini = float('inf')
  for j in range(m):
    if ima[j] <= mini:
      mini = ima[j]
  #print("mini "+str(mini))
  if mini >= x:
    if sum <= ans:
      ans = sum
      return
 
  if i == n:
    return
  for j in range(m):
    newima[j]=ima[j]+lis[i][j+1]
  solve(i+1, newima, sum+lis[i][0])
  solve(i+1, ima, sum)
  
solve(0, ima, 0)
if ans == float('inf'):
  ans = -1
print(ans)

Submission status: Accepted

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

A = [0]*M
for ca in CA:
    for i in range(1,M+1):
        a = ca[i]
        A[i-1]+=a
        
if min(A) < X:
    print(-1)
else:
    K = 2**N
    ans = inf
    for i in range(K):
        b = bin(i)
        b = b.lstrip("0b")
        while (len(b)) < N:
            b = "0"+b
            
        A = [0]*M
        cost = 0
        for j in range(N):
            if b[j] == "1":
                ca = CA[j]
                for k in range(M+1):
                    if k == 0:
                        cost+=ca[k]
                    else:
                        A[k-1] += ca[k]
                        
        if min(A) >= X:
            ans = min(ans,cost)
            
    print(ans)

Submission status: Accepted

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

li = []
ans = 10**10

def make_list():
    global li
    if len(li) == n:
        hantei()
    else:
        li.append(0)
        make_list()
        li.pop(-1)
        li.append(1)
        make_list()
        li.pop(-1)

def hantei():
    global li, ans
    money = 0
    rikai = [0]*m
    for i,e in enumerate(li):
        if e:
            money += c[i]
            for j in range(m):
                rikai[j] += a[i][j]
    if all((rikai[i] >= x for i in range(m))):
        ans = min(ans, money)

make_list()
if ans == 10**10:
    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)]

ans = 1234567890123

for bit in range(1<<n):
    syu = [0]*m
    cost = 0
    for i in range(n):
        if (bit>>i)&1:
            cost += ca[i][0]
            for j in range(1,m+1):
                syu[j-1] += ca[i][j]
    ok = True
    if all(a >= x for a in syu):
        ans = min(ans,cost)
print(ans if ans != 1234567890123 else -1)

Submission status: Accepted

Solution code:
import itertools

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

ans = []
cost = []
for i in range(1, N+1):
    comb_list = itertools.combinations(C, i)
    for comb in comb_list:
        cost_tmp = 0
        ans_tmp = [0] * M
        for c in comb:
            cost_tmp += c[0]
            ans_tmp = [t+c for t, c in zip(ans_tmp, c[1:])]
        cost.append(cost_tmp)
        ans.append(ans_tmp)

ans_result = [all([aa >= X for aa in a]) for a in ans]
try:
    res = min([c for a, c in zip(ans_result, cost) if a])
except:
    print(-1)
    exit()

print(res)

Submission status: Accepted

Solution code:
n, m, x = list(map(int, input().split()))
books = []
dp = [[0]*(m+1) for i in range(2**(n))]
for i in range(n):
    book = list(map(int, input().split()))
    books.append(book)

    
min_cost = -1


for i in range(2**(n)):
    if i == 0:
        continue
    refbook = 0
    keta = 0
    for j in range(13):
        if (i >> j) % 2 == 1:
            refbook += 2**j
            keta = j
        elif i >> j == 0:
            refbook -= 2**(keta)
            break
    refbook = max(0, refbook)   
    checker = True
    for k in range(m+1):
        dp[i][k] = dp[int(refbook)][k] + books[keta][k]
        if k != 0 and dp[i][k]<x:
            checker = False
            
    if checker:
        if min_cost == -1:
            min_cost = dp[i][0]
        else:
            min_cost = min(min_cost, dp[i][0])
          
print(min_cost)

Submission status: Accepted

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

INF = float('INF')
min_cost = INF


def dfs(i, cost, learn):
    if i == N:
        if min(learn) >= X:
            return cost
        else:
            return INF
    else:
        new_learn = [x + y for (x, y) in zip(A[i], learn)]
        cost = min(dfs(i + 1, cost, learn), dfs(i + 1, cost + C[i], new_learn))
        return cost


min_cost = dfs(0, 0, [0] * M)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ans_min = -1
for i in range(2**N):
    ans = 0
    m = defaultdict(int)
    for j in range(N):
        if (i >> j) & 1:
            ans += C[j]
            for index, k in enumerate(A[j]):
                m[index] += k

    if len(m.values()) != 0 and all(v >= X for v in m.values()):
        if ans_min == -1:
            ans_min = ans
        else:
            ans_min = min(ans, ans_min)
print(ans_min)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

N, M, X = map(int, input().split())
CA = np.zeros((N, M + 1))

for i in range(N):
    CA[i, :] = [int(x) for x in input().split()]

min_price = float('inf')
All = [i for i in range(N)]

for x in range(1, N + 1):
    for comb in list(itertools.combinations(All, x)):
        if min(CA[comb, 1:].sum(axis=0)) >= X and CA[comb, 0].sum() < min_price:
            min_price = CA[comb, 0].sum()
        else:
            pass

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

Submission status: Accepted

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

ans = 1234567890123

for bit in range(1<<n):
    syu = [0]*m
    cost = 0
    for i in range(n):
        if (bit>>i)&1:
            cost += ca[i][0]
            for j in range(1,m+1):
                syu[j-1] += ca[i][j]
    ok = True
    if not False in list(map(lambda a: a >= x,syu)):
        ans = min(ans,cost)
print(ans if ans != 1234567890123 else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import copy

def dfs(A, times):
    if times == N:
        if min(A[1:M+1]) >= X:
            ans[0] = min(A[0], ans[0])
        return
    dfs(copy.copy(A), times+1)
    for i in range(M+1):
        A[i] = A[i] + L[times][i]
    dfs(copy.copy(A), times+1)

N, M, X = map(int, input().split())
L = [0] * (N)
for i in range(N):
    L[i] = [int(x) for x in input().split()]

INF = float('inf')
ans = [INF]
tmp = [0] * (M+1)
dfs(tmp, 0)
if ans[0] == INF:
    ans[0] = -1
print(ans[0])

Submission status: Accepted

Solution code:
import numpy as np
import itertools


def main():
    N, M, X = (int(x) for x in input().split())
    A = [[int(x) for x in input().split()] for i in range(N)]
    A.sort()
    a = np.array(A)
    t = []
    ans = []
    for i in range(1, N + 1):
        C = list(itertools.combinations(A, i))
        for c in C:
            k = np.array(c)
            k = k.sum(axis=0)
            ans.append(is_ok(X, k))
    for i in ans:
        if i != -1:
            t.append(i)
    
    if t:
        print(min(t))
    else:
        print(-1)


def is_ok(X, k):
    M = len(k)
    f = list(map(lambda x: x >= X, k[1:M]))
    if False not in f:
        return k[0]
    else:
        return -1


if __name__ == "__main__":
    main()

Submission status: Accepted

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

books = []
books.append(list(map(int, input().split())))
for i in range(n-1):
    item = list(map(int, input().split()))
    books.append(item)

und = [0] * m

for b in books:
    for i in range(m):
        und[i] += b[i+1]

flag = True
for i in range(m):
    if und[i] < x:
        flag = False
        break

if flag == False:
    print(-1)
else:
    b = 0
    ans = float('inf')
    for i in range(2**n-1):
        b +=1
        und = [0] * m
        tmp = format(b,'b').zfill(n)
        tmp_ans = 0
        for j in range(n):
            tmp_ans += books[j][0]*int(tmp[j])
            for k in range(m):
                und[k] += books[j][k+1]*int(tmp[j])

        flag = True
        for k in range(m):
            if und[k] < x:
                flag = False

        if flag and tmp_ans < ans:
            ans = tmp_ans

    print(ans)