Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

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

ans = []
# 全探査
K = 2 # 選択肢の数
for i in range(K**N):
    TF=[0]*N

    for j in range(N):
        TF[N-j-1] = i % K
        i //= K
    
    price = 0
    knowledge = [0]*M
    for j in range(N):
        if TF[j] == 1:
            price += C[j]
            for k in range(M):
                knowledge[k] += A[j][k+1]
        flag = 0
        for k in range(M):
            if knowledge[k] < X:
                flag = 1
        if flag == 0:
            ans.append(price)

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

Submission status: Accepted

Solution code:
import numpy as np

N,M,X = map(int,input().split())
A = np.array([list(map(int,input().split())) for _ in range(N)])
c = 10**10

for i in range(2**N):
    C = np.array([0]*(M+1))
    for j in range(N):
        if ((i >> j) & 1):
            C += A[j]
    for j in range(1,M+1):
        if C[j] < X:
            break
    else:
        c = min(c,C[0])

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [None for _ in range(n)]
a = [None for i in range(n)]
ans = None
for i in range(n):
    c[i], *ai = map(int, input().split())
    a[i] = list(ai)
for p in range(2 ** n):
    y = [0 for _ in range(m)]
    s = format(p, '0{:}b'.format(n))
    cp = 0
    for i, (si, ci) in enumerate(zip(s, c)):
        if si == '1':
            cp += ci
            for j in range(m):
                y[j] += a[i][j]
    for yj in y:
        if yj < x:
            break
    else:
        ans = cp if ans is None else min(ans, cp)
if ans is None:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m,x=INTM()
    ca=[]
    for i in range(n):
        ca.append(LIST())
    inf=10**9
    ans=inf
    for i in range(2**n):
        bag=[]
        for j in range(n):
            if ((i>>j)&1):
                bag.append(ca[j])
        ms=[0]*(m+1)
        for k in bag:
            for l in range(1,m+1):
                ms[l]+=k[l]
        ms=ms[1:]
        flg=1
        #print(bag,ms)
        for j in range(m):
            if ms[j]<x:
                flg=0
        if flg==1:
            cost=0
            for k in bag:
                cost+=k[0]
            ans=min(ans,cost)
    
    if ans==inf:
        print(-1)
    else:
        print(ans)
    
    
if __name__ == '__main__':
    do()

Submission status: Accepted

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,m,x = mp()
cost = []
book = []
inf = int(1e18)
ans = inf
for i in range(n):
    c = lmp()
    cost.append(c[0])
    book.append(c[1:])
cond = [bin(i)[2:].zfill(n) for i in range(2**n)]
for i in range(len(cond)):
    cnt = 0
    al = [0]*(m)
    for j in range(n):
        if cond[i][j] == "1":
            cnt += cost[j]
            for k in range(m):
                al[k] += book[j][k]
    flag = True
    for j in range(m):
        if al[j] < x:
            flag = False
    if flag:
        ans = min(ans,cnt)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product


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

    it = (0, 1)
    pat = list(product(it, repeat=N))

    ans = 10**10
    for p in pat:
        tmp = [0] * M
        flag = [0] * M
        tmp_cost = 0
        for i, b in enumerate(p):
            if b == 1:
                tmp_cost += CA[i][0]
                for j in range(M):
                    tmp[j] += CA[i][j+1]
                    if tmp[j] >= X:
                        flag[j] = 1
                if sum(flag) == M:
                    if ans > tmp_cost:
                        ans = tmp_cost

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

INF = float('inf')
result = INF
for bit in range(1 << N):
    cost = 0
    spec = [0 for _ in range(M)]
    for i in range(N):
        if (bit >> i) & 1:
            cost += C[i]
            for j in range(M):
                spec[j] += A[i][j]

    # print(bin(bit), spec, cost)
    if min(spec) >= X:
        result = min(result, cost)

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

Submission status: Accepted

Solution code:
n,m,y=map(int,input().split())
List=[list(map(int,input().split())) for i in range(n)]
ans=10000000000
for i in range(2**n):
  money=0
  l=[0]*m
  for j in range(n):
    if (i>>j) & 1:
      money+=List[j][0]
      for x in range(m):
        l[x]+=List[j][x+1]
  if all(c>=y for c in l):
    if ans>money:
      ans=money
if ans==10000000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
def resolve():
    n, m, x = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(n)]
    ans = 10**8
    for i in range(2**n):
        book = [0] * n
        cost = 0
        lan = [0] * m
        for j in range(n):
            if (i >> j & 1):
                cost += c[j][0]
                for k in range(m):
                    lan[k] += c[j][k+1]
        ok = True
        for k in range(m):
            if lan[k] < x:
                ok = False
        if ok:
            ans = min(ans, cost)

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

resolve()

Submission status: Accepted

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

C=10**7

for i in range(1<<n):
    c=0
    R=[0]*m
    for j in range(n):
        if i&(1<<j):
            c+=L[j][0]
            for k in range(m):
                R[k]+=L[j][k+1]
    if min(R)>=x:
        C=min(c,C)

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

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N, M, X = ri_()
C = [0] * N
A = []
for i in range(N):
    tmp = ri_()
    C[i] = tmp[0]
    A.append(tmp[1:])
ans = 10 ** 8
for bit in range(2 ** N):
    d = [0] * M
    cost = 0
    for i in range(N):
        if ((bit & (1 << i))):
            cost += C[i]
            for j in range(M):
                d[j] += A[i][j]
    f = 1
    for j in range(M):
        if d[j] < X:
            f = 0
    if f:
        ans = min(ans, cost)
if ans == 10**8:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
# import numpy as np
# import queue
# import heapq


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

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

    min_total_cost = 10**9
    for i in range(2**N):
        total_cost = 0
        learned = [0] * M

        for j in range(N):
            if (i >> j) & 1:
                C, *As = books[j]
                total_cost += C

                for ids, a in enumerate(As):
                    learned[ids] += a

        if min(learned) >= X:
            min_total_cost = min(min_total_cost, total_cost)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, M, K = map(int, input().split())
data = np.array([list(map(int, input().split())) for _ in range(N)])

costs = data[:, 0]
knows = data[:, 1:]

mincost = 1e+9
for i in range(2 ** N):
    bits = np.array([((i >> j) & 1) for j in range(N)])
    sumknows = (knows * bits[:, None]).sum(axis=0)
    if (sumknows >= K).all():
        cost = (costs * bits).sum()
        mincost = min(mincost, cost)
print(mincost if mincost < 1e+9 else -1)

Submission status: Accepted

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M, X = list(map(int,_in[0].split(' ')))  # type:list(int)
    C_A_arr = []
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        C_A_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    condition = [0]*M
    cnt = float('inf')
    for bit in range(1<<N):
        condition = [0]*M
        _cnt = 0
        for i in range(N):
            if bit&(1<<i):
                for j in range(M):
                    condition[j] += C_A_arr[i][j+1]
                _cnt += C_A_arr[i][0]
        if min(condition) >= X:
            cnt = min(cnt,_cnt)
    if cnt == float('inf'):
        cnt = -1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

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)

#bit全探索
ans = float('inf')
for i in range(2**N):
    ac = [-1]*N
    total = [0]*M
    temp = 0
    flg = 0
    for j in range(N):
        if (i>>j)&1:
            ac[j] = 1
    for n in range(N):
        if ac[n]==1:
            temp += C[n]
            for m in range(M):
                total[m] = total[m] + A[n][m]
    for m in range(M):
        if total[m]<X:
            flg = 1
    if flg==0:
        ans = min(ans, temp)
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, M, X = LI()
CA = LRI(N)

ans = INF
for bit in range(1 << N):
    Ms = [0] * M
    tmp = 0
    for i in range(N):
        if (bit >> i) & 1:
            for j in range(M):
                Ms[j] += CA[i][j+1]
            
            tmp += CA[i][0]
    
    flag = True
    for m in Ms:
        if m < X:
            flag = False
    
    if flag:
        ans = min(ans, tmp)

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

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 = 1000000000000
for i in range(2 ** n):
    skill = [0]*m
    cost = 0
    for j in range(n):
        if ((i>>j)&1):
            cost += c[j][0]
            for k in range(m):
                skill[k] += c[j][k+1]
 
                
    if (min(skill)>=x):
        if (ans > cost):
            ans = cost
if (ans != 1000000000000):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

minv = 10**8
for i in range(2 ** N):
    alg = [0]*M
    cost = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k, ca in enu(CA[j]):
                if k == 0:
                    cost += ca
                else:
                    alg[k-1] += ca
    if all([X<=val for val in alg]):
        if cost < minv:
            minv = cost

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

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

import numpy as np

input = sys.stdin.readline


def main():
    N, M, X = map(int, input().split())
    C = [0] * N
    A = np.zeros(shape=(N, M), dtype=int)
    for i in range(N):
        CA = list(map(int, input().split()))
        C[i], A[i] = CA[0], CA[1:]

    ans = float("inf")
    for i in range(1, 13):
        for comb in combinations(range(N), i):
            total = 0
            B = np.zeros(shape=M, dtype=int)
            for j in comb:
                total += C[j]
                B += A[j]
            if all(b >= X for b in B):
                if total < ans:
                    ans = total

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = 10**18

n, m, x = map(int, input().split())
costs = []
a = []
for i in range(n):
    cost, *tmp = map(int, input().split())
    costs.append(cost)
    a.append(tmp)

ans = INF
for i in range(1 << n):
    cost = 0
    ms = [0] * m
    for j in range(n):
        if (i >> j) & 1 == 1:
            cost += costs[j]
            for k in range(m):
                ms[k] += a[j][k]
    can_learn = True
    for j in range(m):
        if ms[j] < x:
            can_learn = False
            break
    if can_learn:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
n,m,co=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(map(int,input().split())))
c=2**n
ans=10**10
for i in range(c):
  li=[]
  a=0
  for j in range(n):  
      if ((i >> j) & 1):  
        li.append(l[j])
        a+=l[j][0]
  z=[0]*m
  for k in range(len(li)):
    for kk in range(m):
      z[kk]+=li[k][kk+1]
  if min(z)>co-1:
    ans=min(ans,a)
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
all_cand = []
for i in range(2**n):
  p_m_list = [False for i in range(n)]
  for j in range(n):
    if ((i >>j) & 1):
      p_m_list[j] = True
  all_cand.append(p_m_list)
c_list = []
for i in range(n):
  c_list.append(list(map(int,input().split())))
result_list = []
for cand in all_cand:
  count = 0
  a_list = [0 for i in range(m)]
  for i in range(len(cand)):
    if cand[i] == True:
      count += c_list[i][0]
      for j in range(1,m+1):
        a_list[j-1] += c_list[i][j]
  if min(a_list) >= x:
    result_list.append(count)
if len(result_list) == 0:
  print(-1)
else:
  print(min(result_list))

Submission status: Accepted

Solution code:
N, M, X=map(int, input().split())
C=[0]*N
A=[]
for i in range(N):
  tmp=list(map(int, input().split()))
  C[i]=tmp[0]
  A.append(tmp[1:])
  
def num2bi(x, k):
  out=format(x, '0'+str(k)+'b')
  return out

cand=[]

tmp=2**N
for i in range(tmp):
  kau=num2bi(i, N)
  nouryoku=[0]*M
  kane=0
  for j in range(N):
    if kau[j]=='1':
      kane+=C[j]
      for k in range(M):
        nouryoku[k]+=A[j][k]
        
  if sum([1 if nouryoku[k]>=X else 0 for k in range(M)])==M:
    cand.append(kane)
    
if len(cand)==0:
  print(-1)
else:
  print(min(cand))

Submission status: Accepted

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

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

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

def sum_i(flg, i):
  result = 0
  for j in range(N):
    result += book[j][i]*flg[j]
  return result

def skill(flg):
  if len(flg)==N:
    for i in range(1,M+1):
      if sum_i(flg,i)<X:
        return ('No', -1)
    return ('Yes', sum_i(flg,0))
  else:
    result_0 = skill(flg+[0])
    result_1 = skill(flg+[1])
    if result_0[0]=='No':
      return result_1
    elif result_1[0]=='No':
      return result_0
    else:
      return ('Yes', min(result_0[1],result_1[1]))

print(skill([])[1])

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]
cand = []
for i in range(2**N):
    ps = [0] * (M + 1)
    for j in range(N):
        if (i >> j) & 1:
            for idx, x in enumerate(data[j]):
                ps[idx] += x
    if all([x >= X for x in ps[1:]]):
        cand.append(ps[0])
if len(cand) == 0:
    print(-1)
else:
    print(min(cand))

Submission status: Accepted

Solution code:
from itertools import product

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

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

ans = 100000000
for buylist in product((0, 1), repeat=N):
    cost = 0
    und = [0]*M
    for idx, x in enumerate(buylist):
        if x == 1:
            cost += CA[idx][0]
            for i in range(1, M+1):
                und[i-1] += CA[idx][i]
    cnt = 0
    for i in range(M):
        if und[i] >= X:
            cnt += 1
    if cnt == M and cost < ans:
        ans = cost
if ans == 100000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

import itertools

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

ans = float('inf')

for case in list(itertools.product('01', repeat=N)):
    val = [0] * M
    price = 0
    # print(case)
    for j in range(N):
        if case[j]=='1':
            price += data[j][0]
            for m in range(M):
                val[m] += data[j][m+1]

    flg = True
    for m in range(M):
        if val[m] < X:
            flg = False
    if flg:
        ans = min(ans, price)

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

Submission status: Accepted

Solution code:
import itertools

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

ans = 10**10
for v in itertools.product([0, 1], repeat=n):
    lst = [0 for i in range(m)]
    money = 0
    for i in range(n):
        if v[i] == 1:
            ci = c[i]
            for j in range(1, m+1):
                lst[j-1] += ci[j]
            money += ci[0]
    if min(lst) >= x:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, X = MAP()
CA = [LIST() for _ in range(N)]
ans = 10**7

for i in range(1<<N):
	i = list("{:b}".format(i).zfill(N))
	cost = 0
	skill = [0]*M
	for j in range(N):
		if i[j] == "1":
			cost += CA[j][0]
			for k in range(M):
				skill[k] += CA[j][k+1]
	if all(x >= X for x in skill):
		ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
from collections import deque

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:])


def book_buy_generator():
    for bit_generator in range(1 << N):
        l = [True if bit_generator & (1 << bit) else False for bit in range(N)]
        yield l


big = 10 ** 7
ans = big

for buy in book_buy_generator():
    learn = [0] * M
    cost = 0
    for book_cost, a, bought in zip(C, A, buy):
        if bought:
            cost += book_cost
            for i in range(M):
                learn[i] += a[i]

    learn_ok = True
    for algorithm in learn:
        if algorithm < X:
            learn_ok = False

    if learn_ok:
        ans = min(ans, cost)

print(ans if ans != big else -1)

Submission status: Accepted

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

ans_init = 10 ** 8
ans = ans_init
for i in range(2 ** n):
    temp_list = [0] * (m + 1)
    for j in range(n):
        if (i >> j) & 1:
            temp_list = [t + b for t, b in zip(temp_list, b_list[j])]
    
    if min(temp_list[1:m+1]) >= x and temp_list[0] < ans:
        ans = temp_list[0]
print(ans if ans != ans_init else -1)

Submission status: Accepted

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

from itertools import combinations


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M, X = map(int, input().split())
    CA = [[] for _ in range(N)]
    for n in range(N):
        CA[n] = list(map(int, input().split()))

    COSTS = []
    for n in range(N):
        for c in combinations(CA, n+1):
            SUM = [0 for _ in range(M)]
            COST = 0
            for ca in c:
                COST += ca[0]
                for m in range(M):
                    SUM[m] += ca[m+1]
            if all(list(map(lambda x: x >= X, SUM))):
                COSTS.append(COST)
    if COSTS:
        print(min(COSTS))
        return
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
from itertools import product
li=[]
ans=10**9
for i in range(n):
    a=list(map(int,input().split()))
    li.append(a)
for p in product([0, 1], repeat = n):
    cnt = [0 for _ in range(m)]
    price=0
    for i in range(n):
        if p[i]==1:
            price+=li[i][0]
            for j in range(m):
                cnt[j]+=li[i][j+1]
    if min(cnt)>=x:
        ans=min(ans,price)
if ans==10**9:
    print("-1")
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C, A = [], []
ans = 1200000
exist = False
for n in range(N):
    li = list(map(int, input().split()))
    C.append(li[0])
    A.append(li[1:])
for b in range(1 << N):
    amount = 0
    understand = [0] * M
    for n in range(N):
        if (b >> n) & 1 == 1:
            amount += C[n]
            for m in range(M):
                understand[m] += A[n][m]
    achieve = True
    for m in range(M):
        if X > understand[m]:
            achieve = False
    if achieve:
        exist = True
        ans = min(ans, amount)
if exist:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations, combinations_with_replacement, product, permutations


import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, X, CA):
    A = [ca[1:] for ca in CA]
    C = [ca[0] for ca in CA]
    ans = INF
    for k in range(1, N+1):
        for i in combinations(range(N), r=k):
            m = [0] * M
            t = 0
            for j in i:
                for k, a in enumerate(A[j]):
                    m[k] += a
                t += C[j]
            if min(m) >= X:
                ans = min(ans, t)
    if ans == INF:
        ans = -1
    return ans


def main():
    N, M, X = read_int_n()
    CA = [read_int_n() for _ in range(N)]
    print(slv(N, M, X, CA))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    Alg = [0]*M
    cost = 0
    for a in A:
        cost += a[0]
        for i in range(M):
            Alg[i] += a[i+1]
    for i in range(M):
        if Alg[i] < X:
            print(-1)
            return

    ans = cost
    for P in product( range(2), repeat=N):
        Alg = [0]*M
        cost = 0
        for i in range(N):
            if P[i] == 0:
                continue
            cost += A[i][0]
            for j in range(M):
                Alg[j] += A[i][j+1]
        check = True
        for i in range(M):
            if Alg[i] < X:
                check = False
                break
        if check:
            if cost < ans:
                ans = cost
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
 
n,m,x = LI()
a = [LI() for i in range(n)]
result = 12000000
for i in range(1 << n):
    c = 0
    val = [0]*m
    for j in range(n):
        if(i & (1 << j)):
            c += a[j][0]
            for k in range(m):
                val[k] += a[j][k+1]
    f = True
    for j in range(m):
        if(val[j] < x):
            f = False
            break
    
    if(f):
        if(result > c):
            result = c

if(result == 12000000):
    print(-1)
else:
    print(result)

Submission status: Accepted

Solution code:
import itertools

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

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


ans=1000000000
for bit in itertools.product([0,1],repeat=n):
  b=[0]*m
  cost=0
  for i in range(n):
    if bit[i]:
      cost+=book[i][0]
      for j in range(1,m+1):
        b[j-1]+=book[i][j]
  k=1
  for i in range(m):
    if b[i]<x:
      k=0
      break
  if k:
    ans=min(ans,cost)
    
if ans==1000000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

a = [[0 for j in range(m)] for i in range(n)]
cost = [0 for j in range(n)]

for i in range(n):
	xx = list(map(int, input().split()))
	cost[i] = xx[0]
	for j in range(m):
		a[i][j] = xx[j + 1]

best_cost = sum(cost) + 1

#print(a)

for mask in range(2**n):
	mm = mask
	knowledge = [0 for i in range(m)]
	total_cost = 0
	book_number = 0 
	#print('start')
	while mask > 0:
		#print(mask)
		if (mask % 2) == 1:
			total_cost += cost[book_number]
			for j in range(m):
				knowledge[j] += a[book_number][j]

		mask = mask // 2
		book_number += 1

	#print(mm, knowledge, total_cost)

	ok = True
	for j in range(m):
		if knowledge[j] < x:
			ok = False 
			break

	if ok:
		#print(mm)
		best_cost = min(best_cost, total_cost)

if best_cost < sum(cost) + 1:
	print(best_cost)
else:
	print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

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:])
A = np.array(A)

ans = sum(C)
flag = False

for i in range(1, N+1):
    for c in combinations(range(N), i):
        k = np.zeros(M)
        cost = 0
        for n in c:
            k += A[n]
            cost += C[n]
        if np.all(k >= X):
            flag = True
            ans = min(ans, cost)

if flag:
    print(ans)
else:
    print(-1)