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(' '))
price, exp = [], [ [] for i in range(N) ]
rst = -1
for i in range(N):
    ls = list(map(int, input().split(' ')))
    price.append(ls[0])
    exp[i] = ls[1:]
for i in range(1 << N):
    price_combi, exp_combi, exp_sum, cnt_ls = [], [], [0] * M, []
    for j in range(N):
        if i >> j & 1:
            price_combi.append(price[j])
            exp_combi.append(exp[j])
    for s in exp_combi:
        for t in range(M):
            exp_sum[t] += s[t]
    [ cnt_ls.append(x) for x in exp_sum if x >= X ]
    if len(cnt_ls) == M:
        if rst == -1:
            rst = sum(price_combi)
        else:
            rst = min(rst, sum(price_combi))
print(rst)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
  c = list(map(int, input().split()))
  C.append(c[0])
  A.append(c[1:])
ans = sum(C) + 1
for n in range(1 << N):
  p = [0 for j in range(M)]
  q = 0
  for i in range(N):
    t = (n >> i) & 1
    q += t * C[i]
    for j in range(M):
      p[j] += t * A[i][j]
  f = 0
  for j in range(M):
    if p[j] < X:
      f = 1
      break
  if f == 0:
    ans = min(ans, q)
if ans > sum(C):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
a = [int(s) for s in input().split()]
N = a[0]
bks = a[1]
bd = a[2]

s = [input().split() for i in range(N)]
anslist = []
for i in range(2**N):
  templist = []
  for t in range(bks+1):
    templist.append(int(0))
  for j in range(N):
    if (i >> j) & 1 == 1:
      for k in range(bks + 1):
        templist[k] += int(s[j][k])
  anslist.append(templist)

ans = int(-1)
flag = int(0)
for i in range(2**N):
  flag = 0
  for j in range(1, bks+1):
    if anslist[i][j] < bd:
      flag = 1
      break
    else:
      pass
  if flag == 0:
      if anslist[i][0] < ans or ans == -1:
        ans = anslist[i][0]

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

data = [[] for _ in range(N)]

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

ans = 12 * (10 ** 5) + 1
ok = False
for i in range(2 ** N):
    v = np.array([0] * (M + 1))
    for j in range(N):
        if (i >> j) & 1:
            v += np.array(data[j])
    x = min(list(v)[1:])
    if X <= x:
        ok = True
        ans = min(ans, v[0])

if ok == True:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = []*N
A = []
for i in range(N):
    b = list(map(int, input().split()))
    C.append(b[0])
    A.append(b[1:])
ans = -1
for i in range(2**N):
    t = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if ans == -1:
            ans = c
        else:
            ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
n,m,x=[int(x) for x in input().split()]
b=[]
for i in range(n):
    c=[int(x) for x in input().split()]
    b.append(c)

import itertools
l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
    l.append(i)

ans=5000000
e=0

for i in range(2**n):
    skill=[0]*m
    p=0
    for j in range(n):
        if l[i][j]==1:
            p+=b[j][0]
            for k in range(m):
                skill[k]+=b[j][k+1]
    s=min(skill)
    if s>=x:
        e=1
        ans=min(ans,p)
if e==1:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
n,m,x=[int(x) for x in input().split()]
book=[]
for i in range(n):
  b=[int(x) for x in input().split()]
  book.append(b)
 
l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
  l.append(i)
 
price=[]
for i in range(2**n):
  check_list=[0]*(m+1)
  for j in range(n):
    if l[i][j]==1:
      for k in range(m+1):
        check_list[k]+=book[j][k]
  check=[]
  for p in range(1,m+1):
    if check_list[p]<x:
      check.append(False)
  if check==[]:
    price.append(check_list[0])
 
if price==[]:
  print("-1")
else:
  print(min(price))

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(' '))
price, exp, rst = [], [ [] for i in range(N) ], -1
for i in range(N):
    ls = list(map(int, input().split(' ')))
    price.append(ls[0])
    exp[i] = ls[1:]
for i in range(1 << N):
    price_combi, exp_combi, exp_sum, cnt_ls = [], [], [0] * M, []
    for j in range(N):
        if i >> j & 1:
            price_combi.append(price[j])
            exp_combi.append(exp[j])
    for s in exp_combi:
        for t in range(M):
            exp_sum[t] += s[t]
    [ cnt_ls.append(x) for x in exp_sum if x >= X ]
    if len(cnt_ls) == M:
        if rst == -1:
            rst = sum(price_combi)
        else:
            rst = min(rst, sum(price_combi))
print(rst)

Submission status: Accepted

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


cost_max = 12 * (10 ** 5)
book_list = []
flag = 0
for i in range(2**n):
    book_num = 0
    book_list = []
    if i == 0:
        continue
    for j in range(n):
        if (i >> j) & 1:
            book_list.append(ca[j])
            book_num += 1
    for j in range(m):
        skill_revel = 0
        for k in range(book_num):
            skill_revel += book_list[k][j+1]
        if skill_revel >= x:
            if j == (m-1) and k == (book_num-1):
                cost = 0
                for l in range(book_num):
                    cost += book_list[l][0]
                if cost <= cost_max:
                    flag = 1 
                    cost_max = cost
            continue
        else:
            break

if flag == 0:
    print(-1)
else:
    print(cost_max)

Submission status: Accepted

Solution code:
#C
import numpy as np
from itertools import combinations
N, M, X=map(int,input().split())
Book = []
for i in range(N):
    Book.append(list(map(int,input().split())))
Comb=[]
for i in range(N+1):
    Comb+=combinations(Book,i)
Sums=[]
for i in Comb[1:]:
    Sum=np.sum(np.array(i),axis=0)
    if all([j >= X for j in Sum[1:]]):
        Sums.append(Sum[0])
if len(Sums)==0:
    print(-1)
else:
    print(sorted(Sums)[0])

Submission status: Accepted

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

costs = []

for i in range(2 ** N):
    t = [0] * M
    cost = 0
    for j in range(N):
        if ((i >> j) & 1) == 1:
            for k in range(M):
                t[k] += BOOK[j][k+1]
            cost += BOOK[j][0]
    
    if all(t[l] >= X for l in range(M)):
        costs.append(cost)

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

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
C = [0]*n
A = []

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

ans = 10**7

for i in range(1 << n):
    res = True
    skill = [0]*m
    money = 0
    for j in range(n):
        if (i>>j)&1:
            for k in range(m):
                skill[k] += A[j][k]
            money += C[j]

    for s in skill:
        if s < x:
            res = False
    
    if res:
        ans = min(ans,money)

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

Submission status: Accepted

Solution code:
from itertools import combinations
import sys

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

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

result = []
for i in range(1, n+1):
  cmb = [s for s in combinations(a, i)]
  for j in cmb:
    total = [0] * (m+1)
    for s in range(i):
      total = [x+y for (x,y) in zip(j[s], total)]
      result.append(total)
      
result.sort()
for k in result:
  price = k[0]
  del k[0]
  if min(k) >= x:
    print(price)
    sys.exit()

print('-1')

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(' '))
price, exp, rst = [], [ []  for i in range(N) ], -1
for i in range(N):
    ls = list(map(int, input().split(' ')))
    price.append(ls[0])
    exp[i] = ls[1:]
for i in range(1 << N):
    price_combi, exp_combi, sum_exp, ls_cnt = [], [], [0] * M, []
    for j in range(N):
        if i >> j & 1:
            price_combi.append(price[j])
            exp_combi.append(exp[j])
    for s in exp_combi:
        for t in range(M):
            sum_exp[t] += s[t]
    [ ls_cnt.append(x) for x in sum_exp if x >= X ]
    if len(ls_cnt) == M:
        if rst == -1:
            rst = sum(price_combi)
        else:
            rst = min(rst, sum(price_combi))
print(rst)

Submission status: Accepted

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

for i in range(N):
    S = list(map(int, input().split()))
    C[i] = S[0]
    A[i] = S[1:]

smallest = None
for i in range(2 ** N):
    sum = 0
    Algo = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            sum += C[j]
            for m in range(M):
                Algo[m] += A[j][m]
    if all(e >= X for e in Algo):
        if smallest == None:
            smallest = sum
        elif sum < smallest:
            smallest = sum

if smallest == None:
    print(-1)
else:
    print(smallest)

Submission status: Accepted

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

for i in range(N):
    S = list(map(int, input().split()))
    C[i] = S[0]
    A[i] = S[1:]

smallest = None
for i in range(2 ** N):
    sum = 0
    string = ""
    Algo = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            sum += C[j]
            for m in range(M):
                Algo[m] += A[j][m]
            string += "1"
        else:
            string += "0"
    # print(Algo)
    # print(string)
    # print(sum)
    if all(e >= X for e in Algo):
        if smallest == None:
            smallest = sum
        elif sum < smallest:
            # print("更新！")
            smallest = sum

if smallest == None:
    print(-1)
else:
    print(smallest)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(' '))
price, exp = [], [ [] for i in range(N) ]
rst = -1
for i in range(N):
    ls = list(map(int, input().split(' ')))
    price.append(ls[0])
    exp[i] = ls[1:]
for i in range(1 << N):
    price_combi, exp_combi, sum_exp, ls_cnt = [], [], [0] * M, []
    for j in range(N):
        if i >> j & 1:
            price_combi.append(price[j])
            exp_combi.append(exp[j])
    for s in exp_combi:
        for t in range(M):
            sum_exp[t] += s[t]
    [ ls_cnt.append(x) for x in sum_exp if x >= X ]
    if len(ls_cnt) == M:
        if rst == -1:
            rst = sum(price_combi)
        else:
            rst = min(rst, sum(price_combi))
print(rst)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

    ans = sys.maxsize
    for mask in range(2 ** N):
        C = 0
        A = [0] * N
        for i in range(N):
            if ((mask >> i) & 1):
                C += ca[i][0]
                A = [a + c for a, c in zip(A, ca[i][1:])]
        if all([i >= X for i in A]):
            ans = min(ans, C)
    if ans != sys.maxsize:
        print(ans)
    else:
        print("-1")

main()

Submission status: Accepted

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

    prices = []
    for bit in range(1 << N):
        price = 0
        understandings = [0] * M
        for i in range(N):
            if bit & (1 << i):
                price += C[i]
                for idx, a in enumerate(A[i], start=0):
                    understandings[idx] += a
        if min(understandings) >= X:
            prices.append(price)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

books = [0]*N
for i in range(N):
    books[i] = list(map(int, input().split()))

cost = float("inf")
for i in range(1<<N):
    scores = [0] * M
    tmpCost = 0

    for j in range(N):
        if (i >> j) & 1:
            tmpCost += books[j][0]
            scores = [scores[k] + books[j][k+1] for k in range(M)]

    isPossible = True
    for j in range(M):
        isPossible &= (X<=scores[j])

    if isPossible:
        cost = min(cost, tmpCost)

if cost < float("inf"):
    print(cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(' '))
price, exp, rst = [], [ [] for i in range(N) ], -1
for i in range(N):
    ls = list(map(int, input().split(' ')))
    price.append(ls[0])
    exp[i] = ls[1:]
for i in range(1 << N):
    price_combi, exp_combi, exp_sum, cnt_ls = [], [], [0] * M, []
    for j in range(N):
        if i >> j & 1:
            price_combi.append(price[j])
            exp_combi.append(exp[j])
    for s in exp_combi:
        for t in range(M):
            exp_sum[t] += s[t]
    [ cnt_ls.append(x) for x in exp_sum if x >= X ]
    if len(cnt_ls) == M:
        if rst == -1:
            rst = sum(price_combi)
        else:
            rst = min(rst, sum(price_combi))
print(rst)

Submission status: Accepted

Solution code:
def main():
	N, M, X = [int(x) for x in input().split(" ")]
	# data[i] = List, data[i][0] = price, data[i][j(1:M)] = skill up of algorithm j
	data = [[int(a) for a in input().split(" ")] for i in range(N)]

	price = []
	for i in range(2 ** N):
		bit_book = list(zero_pad(format(i, 'b'), N))
		p = 0
		level = [0] * M
		for j in range(len(bit_book)):
			if bit_book[j] == "1":
				d = data[j]
				p += d[0]
				level = [l + b for (l, b) in zip(level, d[1:])]
		if min(level) >= X:
			price.append(p)
	if len(price) > 0:
		print(min(price))
	else:
		print(-1)

def zero_pad(s, n):
	s = str(s)
	return ("0" * n + s)[-n:]

main()

Submission status: Accepted

Solution code:
import itertools

def abc167c_skill_up():
    n, m, x = map(int, input().split())
    c = []
    a = []
    for _ in range(n):
        v = list(map(int, input().split()))
        c.append(v[0])
        a.append(v[1:])
    pattern = itertools.product([0,1], repeat=n)
    best = float('inf')
    for p in pattern:
        cost = 0
        skill = [0] * m
        for i, v in enumerate(p):
            if v == 1:
                cost += c[i]
                if cost > best: break
                check = True
                for j in range(m):
                    skill[j] += a[i][j]
                    if skill[j] < x:
                        check = False
                if check:
                    best = cost
                    break
    if best == float('inf'):
        print('-1')
    else:
        print(best)
abc167c_skill_up()

Submission status: Accepted

Solution code:

N, M, X = map(int, input().split(' '))
price, exp, rst = [], [ [] for i in range(N) ], -1
for i in range(N):
    ls = list(map(int, input().split(' ')))
    price.append(ls[0])
    exp[i] = ls[1:]
for i in range(1 << N):
    price_combi, exp_combi, exp_sum, ls_cnt = [], [], [0] * M, []
    for j in range(N):
        if i >> j & 1:
            price_combi.append(price[j])
            exp_combi.append(exp[j])
    for s in exp_combi:
        for t in range(M):
            exp_sum[t] += s[t]
    [ ls_cnt.append(x) for x in exp_sum if x >= X ]
    if len(ls_cnt) == M:
        if rst == -1:
            rst = sum(price_combi)
        else:
            rst = min(rst, sum(price_combi))
print(rst)

Submission status: Accepted

Solution code:
import numpy as np

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

C = []
A = []
for _ in range(N):
    inp = list(map(int, input().split()))
    C.append(inp[0])
    A.append(inp[1:])
A = np.array(A)

for i in range(M):
    if np.sum(A, axis=0)[i] < X:
        print(-1)
        exit()

min_c = 999999999999999
for i in range(2**N):
    item = []
    tmp_c = 0
    for j in range(N):
        if ((i >> j) & 1):
            item.append(A[j])
            tmp_c += C[j]
    if len(item) == 0:
        continue
    for j in range(M):
        if np.sum(item, axis=0)[j] < X:
            break
        if j == M-1:
            if min_c > tmp_c:
                min_c = tmp_c

print(min_c)

Submission status: Accepted

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

ans=float('inf')
for paint_h in range(2**N):
	temp_arr=[0]*(M+1)
	for i in range(N):
		if (paint_h>>i)&1==1:
			temp_arr=[a+b for (a, b) in zip(temp_arr, arr[i])]
	if all(i>=X for i in temp_arr[1:]):
		ans=min(ans, temp_arr[0])
print(ans if ans != float('inf') else -1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Ca = [list(map(int, input().split())) for _ in range(N)]
pattern = []
for i in range(2**N):
    lis = []
    for j in range(N):
        if ((i>>j)&1):
            lis.append(Ca[j])
    pattern.append(lis)

cnt = []
for i in range(2**N):
    g = [0] * (M+1)
    for j in range(len(pattern[i])):
        for k in range(M+1):
            g[k] += pattern[i][j][k]
    if M==1 and g[1]< X:
        continue
    elif M>1 and min(g[1:M+1]) < X:
        continue
    else:
        cnt.append(g[0])
if len(cnt) ==0:
    print(-1)
else:
    print(min(cnt))

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def fn(mask):
    global ans
    cost=0
    b=[0]*(1+m)
    for i in range(n):
        if mask&(1<<i):
            cost+=a[i][0]
            for j in range(1,m+1):
                b[j]+=a[i][j]
    allowed=all([v>=c for v in b[1:]])
    if allowed:ans=min(ans,cost)
n,m,c=list(map(int,stdin.readline().split()))
a=[list(map(int,stdin.readline().split())) for _ in range(n)]
ans=float('inf')
for mask in range(1<<n):
    fn(mask)
print(ans if ans!=float('inf') else -1)

Submission status: Accepted

Solution code:
import numpy as np
N,M,X = map(int,input().split())
C = np.repeat(0, N)
A = np.repeat(0, N*M).reshape(N,M)
for i in range(N):
    x = list(map(int, input().split()))
    C[i] = x[0]
    A[i,:] = x[1:]

ans = np.inf

for _ in range(1<<N):
    # print(format(_, 'b').zfill(H+W))
    choices = [i for i,v in enumerate(format(_, 'b').zfill(N)) if v == '1']
    points = A[choices,:].sum(axis=0)
    if sum(points < X) == 0:
        ans = min(ans, sum(C[choices]))

ans = [ans, -1][np.isinf(ans)]
print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(' '))
price, exp = [], [0] * N
for i in range(N):
    ls = list(map(int, input().split(' ')))
    price.append(ls[0])
    exp[i] = ls[1:]
rst = -1
for i in range(1 << N):
    price_combi, exp_combi, exp_sum, cnt = [], [], [0] * M, []
    for j in range(N):
        if i >> j & 1:
            price_combi.append(price[j])
            exp_combi.append(exp[j])
    for s in range(len(exp_combi)):
        for t in range(M):
            exp_sum[t] += exp_combi[s][t]
    [ cnt.append(i) for i in exp_sum if i >= X ]
    if len(cnt) == M:
        if rst == -1:
            rst = sum(price_combi)
        else:
            rst = min(rst, sum(price_combi))
print(rst)

Submission status: Accepted

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

ans = 12*(10**5)+1
for i in range(2**n):
    a = [0] * m
    cs = 0
    for j in range(n):
        if (i >> j) & 1:
            cs += ca[j][0]
            for k in range(1, m+1):
                a[k-1] += ca[j][k]
    flag = True
    for j in range(m):
        if a[j] < x:
            flag = False
            break
    if flag:
        ans = min(ans, cs)
if ans == 12*(10**5)+1:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(' '))
price, exp, rst = [], [], -1
for i in range(N):
    ls = list(map(int, input().split(' ')))
    price.append(ls[0])
    exp.append(ls[1:])
for i in range(1 << N):
    price_combi, exp_combi, exp_rst, cnt = [], [], [0] * M, []
    for j in range(N):
        if (i >> j) & 1:
            price_combi.append(price[j])
            exp_combi.append(exp[j])
    for s in range(len(exp_combi)):
        for t in range(M):
            exp_rst[t] += exp_combi[s][t]
    [cnt.append(i) for i in exp_rst if i >= X]
    if len(cnt) == M:
        if rst == -1:
            rst = sum(price_combi)
        else:
            rst = min(rst, sum(price_combi))
print(rst)

Submission status: Accepted

Solution code:
import sys
N, M, X = map(int, sys.stdin.readline().split())
D = 12*100001
m = D
Clst = []

for i in range(N):
    Ci = list(map(int, sys.stdin.readline().split()))
    Clst.append(Ci)

for i in range(2**N):
    ch = True
    buy = []
    total = 0
    for j in range(N):
        if ((i>>j)&1):
            buy.append(Clst[j])
            total += Clst[j][0]
            if total >= m:
                ch = False
                break

    if ch:
        for l in range(1,M+1):
            skill = 0
            for k in buy:
                skill = skill + k[l]

            if skill < X:
                ch = False
                break
    
    if ch:
        m = total
    

if m == D:
    print(-1)
else:
    print(m)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
D = 12*100001
m = D
Clst = []

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

for i in range(2**N):
    ch = True
    buy = []
    total = 0
    for j in range(N):
        if ((i>>j)&1):
            buy.append(Clst[j])
            total += Clst[j][0]
            if total >= m:
                ch = False
                break

    if ch:
        for l in range(1,M+1):
            skill = 0
            for k in buy:
                skill = skill + k[l]

            if skill < X:
                ch = False
                break
    
    if ch:
        m = total
    

if m == D:
    print(-1)
else:
    print(m)

Submission status: Accepted

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

book = [0] + [list(map(int, input().split())) for _ in range(N)]
ans = N * 10**5 + 1

for i in range(2**N):
    read = [0] * (N+1)
    rikai = [0] * (M+1)
    cost = 0
    for j in range(N):
        read[j+1] = i%2
        i //= 2
    for j in range(1, N+1):
        if read[j] == 1:
            cost += book[j][0]
            for k in range(1, M+1):
                rikai[k] += book[j][k]
    
    if min(rikai[1:]) >= X:
        ans = min(ans, cost)

print(ans if ans != (N * 10**5 + 1) else -1)

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,m,x = I()
book = [l() for i in range(n)]
money = []

for i in range(2**n):
    ccc = 0
    bag = [0]*(m+1)
    for j in range(n):
        for k in range(m+1):
            if ((i>>j)&1):
                bag[k] += book[j][k]
    for p in range(1,m+1):
        if bag[p] >= x:
            ccc += 1
    if ccc == m:
        money.append(bag[0])

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

Submission status: Accepted

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

INF = 10 ** 8
ans = INF
for selection in range(1 << N):
    price = 0
    values = [0] * M
    for i in range(N):
        if selection & (1 << i):
            x = BOOKS[i]
            price += x[0]
            for j in range(M):
                values[j] += x[j+1]
    if all(v >= X for v in values):
        ans = min(ans, price)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
a = [0]*n
c = []
for i in range(n):
    a[i] = list(map(int,input().split()))
# 0 から (2^n)-1 までループ
for bit in range(1 << n):
    s = [0]*(m+1)

    for i in range(n):
        # bit に i 番目のフラグが立っているかどうか
        if bit & (1 << i):
            for j in range(m+1):
            # フラグが立っているならば sum に加算する
                s[j] += a[i][j]

    if all(s[j] >= x for j in range(1,m+1)):
        c.append(s[0])

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

Submission status: Accepted

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

ans=float('inf')
f=False
for i in range(1,N+1):
    for j in itertools.combinations(range(N), i):
        t=[0]*M
        c=0
        
        for k in j:
            c+=C[k]
            t=[t+a for (t,a) in zip(t,A[k])]
        #print(c,t)
        if M <= len([x for x in t if x>=X]):
            ans=min(ans,c)
            f=True
print(ans if f else -1)

Submission status: Accepted

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

c = [0] * n
a = [[] for _ in range(n)]

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

ans = INF = 1e+9

for s in range(1 << n):
    skill = [0] * m
    money = 0
    for i in range(n):
        # don't buy a book
        if (s >> i) % 2 == 0:
            continue
        money += c[i]
        for j in range(m):
            skill[j] += a[i][j]
    flag = 1
    for k in range(m):
        if skill[k] < x:
            flag = 0
    if flag:
        ans = min(ans, money)
if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

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

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

min_money = -1

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

    count += 1

print(min_money)

Submission status: Accepted

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

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

rikai_list = [0 for _ in range(M)]
cost = 0
ans = -1

for bit in range(1 << N):
    cost = 0
    for i in range(0, N):
        if (bit >> i) & 1 == 1:
            for j in range(M):
                rikai_list[j] += book_list[i][j+1]
            cost += book_list[i][0]
    #print(rikai_list)
    ans_check = 1
    for i in range(M):
        if rikai_list[i] < X:
            ans_check = 0
        rikai_list[i] = 0
        if i == M-1 and ans_check == 1:
            if ans == -1:
                ans = cost
            else:
                ans = min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
import math
N,M,X = map(int,input().split())
#a[i][0]:price of the i-th book
a = [[] for i in range(N)]
for i in range(N):
    a[i] = list(map(int,input().split()))

def is_greater(b):
    for i in b:
        if i < X:
            return False
    return True 
    
cost = math.inf
for i in range(2**N):
    b = [0]*(M+1)
    for j in range(N):
        if ((i >> j)&1):
            for k in range(M+1):
                b[k] += a[j][k]
    if b[0] < cost and is_greater(b[1:]):
        cost = b[0]

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

Submission status: Accepted

Solution code:
import numpy
N,M,X = map(int,input().split())
A = numpy.array([[int(i) for i in input().split()] for _ in range(N)])
ans = 10**8
for i in range(2**N) :
    i = format(i,'b').zfill(N)
    check = numpy.array([0]*(M+1))
    for j in range(N) :
        if i[j] == '0' :
            continue
        check +=  A[j][0:]
    if all (check[m] >= X for m in range(1,M+1)) :
        ans = min(ans,check[0])

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

Submission status: Accepted

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

ans=10**5*N+1
for maskN in range(1<<N):
  cost=0
  level=[0]*M
  for n in range(N):
    if (maskN>>n&1):
      cost+=C[n]
      for m in range(M):
        level[m] += A[n][m]
  for l in level:
    if l < X:
      break
  else:
    ans=min(ans, cost)
print(f'{ans if ans!=10**5*N+1 else "-1"}')

Submission status: Accepted

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

ans=10**18
for maskN in range(1<<N):
  cost=0
  level=[0]*M
  for n in range(N):
    if (maskN>>n&1):
      cost+=C[n]
      for m in range(M):
        level[m] += A[n][m]
  for l in level:
    if l < X:
      break
  else:
    ans=min(ans, cost)
print(f'{ans if ans!=10**18 else "-1"}')

Submission status: Accepted

Solution code:
#bit全探索

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

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