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:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,x = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(n)]
    ans = float("inf")

    for b in range(1<<n):
        cost = 0
        k = [0]*m
        for i in range(n):
            if b&(1<<i): #i番の本を選んでいたら
                cost += s[i][0] #i番の本の値段を足す
                for j in range(m):
                    k[j] += s[i][j+1] #選んだ本で得られる理解度をトピックごとに合計していく
        if cost < ans and all([i >= x for i in k]):
            ans = cost
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

def readlines(n):
    for _ in range(n):
        yield list(map(int, input().split()))

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

    books = np.array(list(readlines(N)))
    ans = np.inf
    for bit in product([0, 1], repeat=N):
        comb_sum = np.dot(np.array(bit), books)
        if all(comb_sum[1:] >= X):
            ans = min(ans, comb_sum[0])

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


main()

Submission status: Accepted

Solution code:
import sys
import itertools
n, m, x=map(int, input().split())
text = [list(map(int, i.strip('\n').split())) for i in sys.stdin]
num_tex = [i for i in range(1, len(text) + 1)]
all_c = []
for comb in num_tex:
    for v in itertools.combinations(text, comb):
        sum_a = []
        for j in range(1, len(v[0])):
            sum_a.append(sum([v_[j] for v_ in v]))
        if all([x <= sum_a_ for sum_a_ in sum_a]):
            all_c.append(sum([v_[0] for v_ in v]))
if len(all_c)!=0:
    print(sorted(all_c)[0])
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
t = [ i + 1 for i in range(0,n)]
res = []
for i in range(n):
    c_a = list(map(int,input().split()))
    res.append(c_a)
import itertools
choice = []
def all_choice(x,n):
    for i in x:
        for j in itertools.combinations(range(0,n), i):
            choice.append(j)
    return choice
all_choice = all_choice(t,n)
count = []
for a in all_choice:
    res_0 = np.array([res[i] for i in a])
    flag = 0
    for i in range(m):
        if sum([t[i+1] for t in res_0]) < x:
            flag = 1
            break
    if flag == 0:
        count.append(sum([t[0] for t in res_0]))
if len(count)==0:
    print(-1)
else:
    print(min(count))

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
c=[0]*n
a=[[0 for i in range(m)] for j in range(n)]
current_skill=[0]*m
INF=9999999
min_money=INF


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

current_money=0

for i in range(1 << n):
    bug=[]
    for j in range(n):
        if (i>>j) &1:
            bug.append(j)
    current_skill=[0]*m
    current_money=0
    for chosen_set_num in bug:
        current_money+=c[chosen_set_num]
        for each_book_num in range(m):
            current_skill[each_book_num]+=a[chosen_set_num][each_book_num]
            

        if all(status >=x for status in current_skill ):
            min_money=min(min_money,current_money)
            continue
if min_money==INF:
    min_money=-1
print(min_money)

Submission status: Accepted

Solution code:
def dfs(bit):
    if len(bit)==N:
        c=0
        s=[0 for _ in range(M)]
        for i in range(N):
            c+=A[i][0]*bit[i]
            if bit[i]==1:
                for j in range(M):
                    s[j]+=A[i][j+1]
                cond=True
                for k in range(M):
                    if s[k]<X:
                        cond=False
                        break
                if cond:
                    ans.append(c)
        return

    else:
        for i in range(2):
            bit.append(i)
            dfs(bit)
            bit.pop()
    
N,M,X=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N)]

ans=[]

dfs([])

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

Submission status: Accepted

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

# bit全探索
ans = -1
for i in range(2 ** N):
    p = [0 for _ in range(M)]
    kakaku = 0
    for j in range(N):
        if (i >> j) & 1:
            kakaku += box[j][0]
            for n, k in enumerate(box[j][1:]):
                p[n] += k
    if all(el >= X for el in p):
        if ans == -1:
            ans = kakaku
        else:
            ans = min(ans, kakaku)
print(ans)

Submission status: Accepted

Solution code:
def skill_up(books_costs, books_knowledge, target):
    def add_book(aggr_knowledge, aggr_cost, idx):
        for i, algo in enumerate(books_knowledge[idx]):
            aggr_knowledge[i] += algo
        aggr_cost += books_costs[idx]
        return aggr_knowledge, aggr_cost

    def remove_book(aggr_knowledge, aggr_cost, target, idx):
        potential_comb = True
        for i, algo in enumerate(books_knowledge[idx]):
            aggr_knowledge[i] -= algo
            potential_comb &= aggr_knowledge[i] >= target
        aggr_cost -= books_costs[idx]
        return aggr_knowledge, aggr_cost, potential_comb
    
    def min_cost_skill_up(aggr_knowledge, aggr_cost, idx, target):
        if idx == len(books_knowledge):
            return aggr_cost

        min_cost = aggr_cost

        min_cost = min(min_cost, min_cost_skill_up(aggr_knowledge, aggr_cost, idx+1, target))

        aggr_knowledge, aggr_cost, potential_comb = remove_book(aggr_knowledge, aggr_cost, target, idx)
        if potential_comb:
            min_cost = min(min_cost, min_cost_skill_up(aggr_knowledge, aggr_cost, idx+1, target))
        aggr_knowledge, aggr_cost = add_book(aggr_knowledge, aggr_cost, idx)

        return min_cost

    aggr_knowledge = [0 for _ in range(len(books_knowledge[0]))]
    aggr_cost = 0
    for i in range(len(books_knowledge)):
        aggr_knowledge, aggr_cost = add_book(aggr_knowledge, aggr_cost, i)

    if not all([algo_knowledge >= target for algo_knowledge in aggr_knowledge]):
        return -1

    return min_cost_skill_up(aggr_knowledge, aggr_cost, 0, target)


book_count, algorithm_count, target = map(int, input().split(' '))
books_knowledge = [[0 for _ in range(algorithm_count)] for _ in range(book_count)]
books_costs = [0 for _ in range(book_count)]

for i in range(book_count):
    book = list(map(int, input().split(' ')))
    books_costs[i] = book[0]
    books_knowledge[i] = book[1:]

print(skill_up(books_costs, books_knowledge, target))

Submission status: Accepted

Solution code:
import itertools

N, M, X = map(int, input().split())
List = [list(map(int, input().split())) for n in range(N)]
INF = 10**7
ans = INF
C_pro = list(itertools.product([0,1], repeat=N))

for c_pro in C_pro:
    count = 0
    cost = 0
    ans_list = [0 for i in range(M)]
    for c in c_pro:
        if c == 1:
            cost += List[count][0]
            ans_list = [answ+list for answ, list in zip(ans_list,List[count][1:])]
        count += 1
    ok = True
    for i in range(len(ans_list)):
        if ans_list[i] < X:
            ok = False
            break
    if ok:
        ans = min(ans, cost)
    

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
#
total_all = []
for i in range(2**n):
    b = [0]*m
    total = 0
    check = 'OK'
    for j in range(n):
        if ((i >> j) & 1):
            total += a[j][0]
            for k in range(1,m+1):
                b[k-1] += a[j][k]
    for l in range(m):
        if b[l] < x:
            check = 'NG'
            break
    if check == 'OK':
        total_all.append(total)
if len(total_all) == 0:
    print(-1)
else:
    print(min(total_all))

Submission status: Accepted

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

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

ans = 10 ** 10

for state in range(1 << N):
    price = 0
    compre = [0 for _ in range(M)]
    for i in range(N):
        if ((state >> i) & 1) == 1:
            # use
            price += cost[i]
            for j in range(M):
                compre[j] += A[i][j]

    check = True
    for i in range(M):
        check &= (compre[i] >= X)
    if check:
        ans = min(ans, price)

if ans == 10 ** 10:
    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 range(2**N):
    # 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':
        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:
from itertools import product
import numpy as np

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

def calc(p):
    cnt = np.dot(np.array(list(p)), np.array(A))
    return np.dot(np.array(list(p)), np.array(C)) if all(i >= X for i in cnt) else 10 ** 30

ans = 10 ** 30
for p in product(range(2), repeat=N):
    ans = min(ans, calc(p))

print(ans if ans < 10 ** 30 else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(n)]
c = [ca[i][0] for i in range(n)]
a = [ca[i][1:] for i in range(n)]
ans = 0
cost = sum(c)
for i in range(2**n):
    kari = 0
    skill = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            kari += c[j] 
            skill = [x + y for (x,y) in zip(skill,a[j])]
            
    if all([z >= x for z in skill ]):
        cost= min(cost,kari)
        ans += 1
        
if ans == 0:
    print(-1)
else:
    print(cost)

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
A = [[int(x) for x in input().split()] for _ in range(N)]
 
INF = float('inf')
ans = INF

#print(A)
for i in range(2**N):
    tmp = [0 for _ in range(M+1)]
    b = bin(i)[2:].zfill(N)
    #print(b)
    
    for n in range(N):
        for m in range(M+1):
            tmp[m] += A[n][m] * int(b[N-1-n])
    #print(tmp[1:])
 
    if min(tmp[1:]) >= X:
        ans = min(ans, tmp[0])
 
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

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

add = []

for i in range(2**n):
    skill = [0]*(m+1)
    for j in range(n):
        if ((i>>j) & 1):
            skill = list(map(sum, zip(skill, ca[j])))
    if min(skill[1:])>=x:
        add.append(skill)

if add:
    add.sort()
    print(add[0][0])
else:
    print(-1)

Submission status: Accepted

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

INF = float('inf')
ans = INF

for i in range(2**N):
    tmp = [0 for _ in range(M+1)]
    b = bin(i)[2:].zfill(N)
    
    for n in range(N):
        for m in range(M+1):
            tmp[m] += A[n][m] * int(b[N-1-n])

    if min(tmp[1:]) >= X:
        ans = min(ans, tmp[0])

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

Submission status: Accepted

Solution code:
def check(learn_total):
    for i in range(m):
        if learn_total[i] < x:
            return False  
    return True 

def calc_price(bit):
    price_total = 0 
    learn_total = [0] * m 

    for i in range(n):
        if (bit >> i) & 1:  
            price_total += c[i]  
            learn = a[i]  
            for j, la in enumerate(learn): 
                learn_total[j] += la

   
    if check(learn_total):
        return price_total 
    else:
        return INF

if __name__ == '__main__':
    n, m, x = list(map(int, input().split()))

    # 空のリストを作って、appendで追加していきます
    c = []  # 参考書の値段です
    a = []  # 各参考書に入る理解度です

    for i in range(n):
        c_temp, *a_temp = list(map(int, input().split()))  # こうすると、2つ目以降をリストで受け取れます
        c.append(c_temp)
        a.append(a_temp)

    INF = float("inf")
    ans = INF

    for bit in range(1 << n):
        price = calc_price(bit)  # 条件を満たすならそのときの値段、満たさないならINFが返ってきます
        ans = min(ans, price)  # 答えを更新します

    if ans == INF:
        print(-1)  # どうやっても条件を満たせなかった
    else:
        print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')

def dfs(i, C):
    if i == N:
        if min(C[1:]) >= X:
            return C[0]
        else:
            return INF
    res = INF
    tmp = [0 for _ in range(M+1)]
    for bit in range(2):
        for j in range(M+1):
            tmp[j] = C[j] + A[i][j] * bit
        res = min(res, dfs(i+1, tmp))
    return res

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

ans = dfs(0, [0 for _ in range(M+1)])
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
#bit全探索を使う。今回は, 2 ** n通り調べることになる
N, M, X = map(int, input().split())

C = []
A = []
for i in range(N):
    t = list(map(int, input().split()))
    C.append(t[0])
    A.append(t[1:])
ans = -1
for i in range(1 << N): # i は 0 ~ 2 ** n - 1 ; iが買う本の組み合わせを表すbit列となる
    experience = [0] * M
    cost = 0
    #~それぞれの本の組み合わせについて、値段、最終的な経験値が Xを超えているか調べるブロック~
    for j in range(N):
        if (i >> j) & 1 == 0: #(i >> j) & 1 は 、i を右に jビットシフトし、1がj番目に含まれているかを調べる操作 (j は 0 から N まで動かす、つまり、長さNのbit列に1が何個あるかを数えている)
            continue 
        cost += C[j] #bit列のj番目に1があった場合, それはj番目の本を選んでいるわけだから,その本の値段を加算する
        for k in range(M):   
            experience[k] += A[j][k]
        if all(x >= X for x in experience): #すべてが X以上であれば
            if ans == -1:
                ans = cost
            else:
                ans = min(ans, cost) # より安いものを得る
print(ans)

Submission status: Accepted

Solution code:
N, M, X = [int(n) for n in input().split()]

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

ans = 10**10

for i in range(2**N):
  cost = 0
  skills = [0] * M
  for j in range(N):
    if ((i >> j) & 1):
      #print(i, j)
      for k in range(M):
        skills[k] += CA[j][1+k]
      cost += CA[j][0]
  #print("skills", skills)
  if all([n >= X for n in skills]):
  	ans = min(ans, cost)
  #print("ans", ans)
if ans == 10**10:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

for i in range(2**n):
  money=0
  tm=[0]*m
  for j in range(n):
    if (i>>j)&1==0:
      continue
    money+=c[j]
    for k in range(m):
      tm[k]+=a[j][k]
    if all(xx>=x for xx in tm):
      if result==-1:
        result=money
      else:
        result=min(money,result)
print(result)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np


N, M, X = list(map(int, input().split()))
INF = 10**5 * 12 + 1
books = np.array([list(map(int, input().split())) for i in range(N)])
ans = INF
for selection in product([0, 1], repeat=N):
    selection = np.array(selection).reshape(N, 1)
    res = (books * selection).sum(axis=0)
    if min(res[1:]) >= X:
        ans = min(ans, res[0])
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
l = []
for i in range(n):
    ca = list(map(int,input().split()))
    l.append(ca)
ans = 9999999999
for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(l[j])
    skill = [0]*m
    enough = [0]*m
    money = 0
    for sub in bag:
        money += sub[0]
        for k in range(1,m+1):
            skill[k-1] += sub[k]
            if skill[k-1]>=x:
                enough[k-1] += 1
        if 0 not in enough:
            if ans>money:
                ans = money
if ans == 9999999999:
    
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
import numpy as np


def list_add(l):
    wrk = np.array(l[0], dtype=int)
    for i in l[1:]:
        wrk = np.array(wrk, dtype=int) + np.array(i, dtype=int)
    return wrk.tolist()


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

ans = -1

for i in range(1, n+1):
    c_list = list(itertools.combinations(l, i))
    for c in c_list:
        t = list_add(c)
        ok = True
        for c in t[1:]:
            if c < x:
                ok = False
        if ok:
            if ans == -1 or ans > t[0]:
                ans = t[0]
print(ans)

Submission status: Accepted

Solution code:
import itertools
def main():
    n,m,x = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(n)]
    ans = 10**9

    for i in range(2**n):
        bit = format(i, f'0={n}b')
        rikaido = [0]*m
        kingaku = 0
        for num, val in enumerate(bit):
            if val == '1':
                kingaku += c[num][0]
                for num2, val2 in enumerate(c[num][1:]): rikaido[num2] += val2
        if min(rikaido) >= x:
            ans = min(kingaku, ans)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

N,M,X = map(int,readline().split())
books = [None] * N
for i in range(N):
  data = list(map(int,readline().split()))
  cost = data[0]
  point = data[1:]
  books[i] = [cost,point]
  
# M個から1個以上M個以下を選ぶ。選ぶ数でループ
INF = 10 ** 10
ans = INF
import itertools
for i in range(1, N + 1):
  for target in itertools.combinations(books, i):
    skills = [0] * M
    totalcost = 0
    for t in target:
      totalcost += t[0]
      point = t[1]
      for j in range(len(point)):
        skills[j] += point[j]
    if totalcost < ans:
      for j in range(len(skills)):
        if skills[j] < X:
          break
      else:
        ans = totalcost
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools

#n桁のm値のbitを生成
def bit(n, m):
  bit_list = list(itertools.product([i for i in range(m)], repeat=n))
  return bit_list

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

ans = 10 ** 10
bits = bit(N, 2)
for bit_ptr in  bits:
  und_algo = [0 for _ in range(M)]
  tmp = 0
  for i in range(N):
    if bit_ptr[i] == 1:
      for j in range(M):
        und_algo[j] += A[i][j+1]

      tmp += A[i][0]
  
  flag = True
  for i in range(M):
    if und_algo[i] < X:
      flag = False

  if flag:
    ans = min(ans, tmp)

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

Submission status: Accepted

Solution code:
import itertools
def main():
    n,m,x = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(n)]
    # c = sorted(c, key=lambda x:sum(x[1:])/x[0], reverse=True)
    ans = 10**9
    possible = False

    for i in range(1, n+1):
        for j in itertools.combinations(c,i):
            rikaido = [0]*m
            kingaku = 0
            for k in j:
                kingaku += k[0]
                for num, val in enumerate(k[1:]):
                    rikaido[num] += val

            if min(rikaido) >= x:
                ans = min(ans, kingaku)
    print(-1) if ans == 10**9 else print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,x=map(int, input().split())
c = []
a = []
for i in range(n):
    t = [int(j) for j in input().split()]
    c.append(t.pop(0))
    a.append(t)

me = [x] * m
min = sum(c)+1
cost = 0

def f(me, books, ctbl, cost):
    global min 
    if len(books) == 0:
        return
    for i,b in enumerate(books):
        t = tuple(map(lambda x:x[0]-x[1], zip(me, b)))
        if len(tuple(filter(lambda x:x>0, t))) > 0:
            f(t, books[i+1:], ctbl[i+1:], cost+ctbl[i])
        else:
            if min > cost+ctbl[i]:
                min = cost+ctbl[i]
    f(me, books[1:], ctbl[1:], cost)

f(me, a, c, 0)
if sum(c) < min:
    print(-1)
else:
    print(min)

Submission status: Accepted

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

a = [input().split() for i in range(n)]
c = [a[i].pop(0) for i in range(n)]

INF = 1001001001
ans = INF
for s in range(1<<n):
    cost = 0
    d = [0]*m
    for i in range(n):
        if s>>i & 1:
            cost += int(c[i])
            for j in range(m):
                d[j] += int(a[i][j])
    ok = True
    for j in range(m):
        if d[j] < x:
            ok = False
    if ok:
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
import numpy
import sys

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

row_sum = numpy.sum(book, axis=0)
if(min(row_sum)<X):
  print("-1")
  sys.exit()

result=-1
for i in range(2**N):
  t=[0]*M
  money=0
  for j in range(N):
    # 右から数えてj番目の本が0の場合はcontinue,1の場合は購入
    if (i>>j)&1==0:
      continue
    money+=book[j][0]
    for k in range(1,M+1):
      t[k-1]+=book[j][k]
  # すべての習熟度がX以上ならば
  if all(xx>=X for xx in t):
    if(result==-1):
      result=money
    else:
      result=min(result,money)
print(result)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0]*N
A = [[0]*(M+1)]*N
cost = 1
for i in range(N):
  A[i] = list(map(int, input().split()))
  cost += A[i][0]
cost_temp = cost 
for i in range(2**N):
  flag = True
  B = [False]*N
  D = [0]*(M+1)
  for j in range(N):
    if ((i >> j) & 1):
      B[j]=True
  for n in range(N):
    if B[n]:
      for m in range(M+1):
        D[m] += A[n][m]
  for m in range(M):
    if D[m+1]<X:
      flag = False
      break
  if flag and cost > D[0]:
    cost = D[0]
if cost == cost_temp:
  print(-1)
else:
  print(cost)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(n)]
result=-1
for i in range(2**n):
  t=[0]*m
  money=0
  for j in range(n):
    if (i>>j)&1==0:
      continue
    money+=c[j][0]
    for k in range(1,m+1):
      t[k-1]+=c[j][k]
  if all(xx>=x for xx in t):
    if result==-1:
      result=money
    else:
      result=min(result,money)
print(result)

Submission status: Accepted

Solution code:
#coding :utf-8

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

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

for i in range(1<<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 result==-1:
      result=c
    else:
      result=min(result,c)

print(result)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
C, A = list(map(lambda x: x[0], A)), list(map(lambda x: x[1:], A))
ans = 10**18
for i in range(2**n):
    M = [0]*m
    cost = 0
    for j in range(n):
        if (i>>j)&1:
            cost += C[j]
            for k in range(m):
                M[k] += A[j][k]
                
    
    if all([mm >= x for mm in M]): ans = min(ans, cost)
print(ans if ans!=10**18 else '-1')

Submission status: Accepted

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

ans = float('inf')

for i in range(1<<N):
  a = [0] * (M+1)

  for j in range(N):
    if ((i >> j) & 1):
      for x, k in enumerate(CA[j]):
        a[x] += k

  if all(a >= X for a in a[1:]):
    ans = min(ans, a[0])

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

Submission status: Accepted

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

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

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

cmin = sum(c) + 1
tassei = False

for i in range(1<<n):
  rikai = [0 for i in range(m)]
  cnow = 0
  for j in range(n):
    if i & (1<<j):
      cnow+=c[j]
      for mnow in range(m):
        rikai[mnow]+=a[j][mnow]
  if min(rikai)>=x:
    tassei = True
    cmin = min(cmin, cnow)

if tassei:
  print(cmin)
else:
  print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = 10000000000

for i in range(1, n+1):
	for cb in list(combinations(rng,i)):
		r = [0]*m
		cout = 0
		for j in cb:
			cout+=c[j]
			for k in range(m):
				r[k]+=a[j][k]
		if min(r)>=x:
			ans = min(ans, cout)
		
print(ans if ans !=10000000000 else -1)

Submission status: Accepted

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

for j in range(n):
    c.append([int(i) for i in input().split()])
'''
und_list=[]
for i in range(n):
    for j in range(1,m+1):
        und_list[j-1] += c[i][j]
if min(und_list) < x:
    print(-1)
else:
'''
ans=-1
for i in range(2**n):
    und_list=[0]*m
    sum_money=0
    for j in range(n):
        if((i >> j)&1):
            for k in range(m):
                und_list[k] += c[j][k+1]
            sum_money+=c[j][0]
    if min(und_list)>=x:
        if ans==-1:
            ans= sum_money
        elif ans > sum_money:
            ans=sum_money
print(ans)

Submission status: Accepted

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

m = []
A = []
for x in range(N):
  A = list(map(int, input().split()))
  m.append(A)

ans = 1000000007
for i in range(2**N):
  l = []
  total = 0
  for j in range(N):
    if ((i >> j) & 1):
      l.append(m[j])
  a = [0] * (M+1)
  for x in l:
    for i, k in enumerate(x):
      a[i] += k

  found = True
  for i, x in enumerate(a):
    if i >= 1:
      if x < X:
        found = False

  if found:
    ans = min(ans, a[0])

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

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)]
for i in range(1,M+1):
    count=0
    for j in range(N):
        count+=ca[j][i]
    if count<X:
        print(-1)
        exit()

ans = []
for z in product((0, 1), repeat=N):#bit全探索のくみあわせを勝手に作ってくれるので使うとよい
    count=0
    count2=[0]*M
    for i in range(N):
        if z[i]==1:
            count+=ca[i][0]
            for j in range(1,M+1):
                count2[j-1]+=ca[i][j]
    
    for i in range(M):
        if count2[i]<X:
            break
    else:
        ans.append(count)
print(min(ans))

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)]
for i in range(1,M+1):
    count=0
    for j in range(N):
        count+=ca[j][i]
    if count<X:
        print(-1)
        exit()

ans = 10**9
for z in product((0, 1), repeat=N):#bit全探索のくみあわせを勝手に作ってくれるので使うとよい
    count=0
    count2=[0]*M
    for i in range(N):
        if z[i]==1:
            count+=ca[i][0]
            for j in range(1,M+1):
                count2[j-1]+=ca[i][j]
    
    for i in range(M):
        if count2[i]<X:
            break
    else:
        ans=min(count,ans)
print(ans)

Submission status: Accepted

Solution code:
import copy
s = input().split()

n = int(s[0])
m = int(s[1])
x = int(s[2])

s_list = [[0 for i in range(m+1)] for j in range(n)]

for i in range(n):
    r = input().split()
    s_list[i][0] = int(r[0])
    for j in range(1,m + 1):
        s_list[i][j] = int(r[j])


gen = [0] * (m + 1)
kakaku = -1

for i in range(2 ** n):
    kari = copy.copy(gen)
    for j in range(n):
        if ((i >> j) & 1):
            for l in range(m+1):
                kari[l] += s_list[j][l]

    check = 0
    for j in range(1,m + 1):
        if kari[j] < x:
            check = 1
            break
    if check == 0 and (kari[0] < kakaku or kakaku == -1):
        kakaku = kari[0]

print(kakaku)

Submission status: Accepted

Solution code:
n, m, x0 = list(map(int, input().split()))
c = [0] * n
a = [[0]*m for i in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    c[i] = tmp[0]
    a[i] = tmp[1:]

b = [[0]*m for i in range(2**n)]
money = [0] * (2**n)

list2n = [list(f"{i:0{n}b}") for i in range(2**n)]

for i, x in enumerate(list2n):
    for j in range(n):
        money[i] += c[j] * int(x[j])
        for k in range(m):
            b[i][k] += a[j][k] * int(x[j])
            
ans = 1e10
for i in range(2**n):
    flag = True
    for j in range(m):
        if b[i][j] < x0:
            flag = False
            break
    if flag == True:
        ans = min(ans, money[i])

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