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:
import numpy as np

min_price = -1
C = []
A = []
N = 0
X = 0

def check_flag(data, now, price):
    global C, A, N, X, min_price
    if now == N or sum(data >= X) == len(data):
        # print(data, now, price)
        if sum(data >= X) == len(data) and (min_price == -1 or min_price > price):
            min_price = price
        return

    for n in range(now, N):
        check_flag(data+A[n], n+1, price+C[n])
    
def main():
    global C, A, N, X, min_price
    N, M, X = [int(x) for x in input().split()]
    for _ in range(N):
        temp = [int(x) for x in input().split()]
        C.append(temp[0])
        A.append(temp[1:])
    A = np.array(A)
    check_flag(np.array([0] * M), 0, 0)
    print(min_price)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

cost = 0
books = []

for _ in range(N):
    books.append([int(i) for i in input().split()])
    
book_numbers = [i for i in range(0, N)]

cnt = set()

for i in range(1, N+1):
    c = list(itertools.combinations(book_numbers, i))
    for j in range(len(c)):
        combi = c[j]
        after_study = [0 for _ in range(M + 1)]
        for k in combi:
            for l in range(len(books[k])):
                after_study[l] += books[k][l]
                
        cost = after_study.pop(0)
        if min(after_study) >= X:
            cnt.add(cost)

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

Submission status: Accepted

Solution code:
from itertools import combinations as cmb
bookN, algoN, score = map(int, input().split())

Books = []
for i in range(bookN):
  Book = list(map(int, input().split()))
  Books.append(Book)

money = 12 * 10 ** 5 + 1
for k in range(1, bookN +1):
  for books in cmb(Books, k):
    price_algo = [0] * (algoN +1)
    for book in books:
      for item in range(len(book)):
        price_algo[item] += book[item]
    for item_ in range(1, algoN +1):
      if price_algo[item_] < score:
        break
    else:
      if price_algo[0] < money:
        money = price_algo[0]

if money == 12 * 10 ** 5 + 1:
  money = -1
print(money)

Submission status: Accepted

Solution code:
# C
# Skill Up

import itertools
import numpy as np

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

data_tensor = np.empty((n,m))
c_list = np.empty((n,1))

ans = 100000000
flag = True

for i in range(n):
    _list = list(map(int, input().split()))
    c_list[i], data_tensor[i] = _list[0], _list[1:]
    
buy_tensor = itertools.product([0,1],repeat=n)

for _list in buy_tensor:
    _list_np = np.array(_list)
    _list_np = _list_np.reshape(-1,1)
    _sum_list = np.sum(data_tensor * _list_np, axis=0)
    if np.min(_sum_list) >= x:
        _ans = np.sum(c_list * _list_np)
        if _ans < ans:
            ans = int(_ans)
            flag = False
        
if flag:
    ans = -1

print(ans)

Submission status: Accepted

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

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

ans = []

for bit in range(2 ** len(c)):
  u = []
  for j in range(len(c)):
    if (bit >> j) & 1:
      u.append(c[j])

  f = [False] * m
  for h in range(m):
    mm = 0
    for z in u:
      mm += z[h+1]

    if mm == x or mm > x: 
      f[h] = True

  if f.count(True) == m:
    jj = 0
    for i in u:
      jj += i[0]
    ans.append(jj)

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

Submission status: Accepted

Solution code:
#author: raghav_0901
from math import *

mod = (10**9) + 7


def _in():
    return [int(x) for x in input().split(' ')]


arr = []
MAX = 10**10


def solve(n, m, x, s, skill):

    # check valid
    flag = True
    # print(s, skill)
    for i in skill:
        if i < x:
            flag = False
    if(flag):
        return 0

    if(s == n):
        return MAX

    a2 = solve(n, m, x, s + 1, skill)

    for i in range(m):
        skill[i] = skill[i] + arr[s][i + 1]

    a1 = solve(n, m, x, s + 1, skill) + arr[s][0]

    for i in range(m):
        skill[i] = skill[i] - arr[s][i + 1]

    return min(a1, a2)


def main():
    n, m, x = _in()
    for i in range(n):
        arr.append(_in())
    skill = [0] * (m)
    ans = solve(n, m, x, 0, skill)
    print(ans if ans < MAX else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(2 ** n):
    value_list = [0]*(m+1)
    value = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            value.append(data_list[j])

    for i in range(len(value)):
        for j in range(m+1):
            value_list[j] += value[i][j]

    if min(value_list[1:]) >= x and value_list[0] < price:
        price = value_list[0]
    
    
if price == 12000000:
    print(-1)
else:
    print(price)

Submission status: Accepted

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

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

for i in range(2**n):
  ans = [0 for i in range(m+1)]
  count = 0
  for j in range(n):
    if (i>>j)&1:
      for l in range(m+1):
        ans[l] += box[j][l]
  for k in range(1,m+1):
    if ans[k]>=x:
      count += 1
  if count == m:
    anss.append(ans[0])
if len(anss) == 0:
  print(-1)
else:
  print(min(anss))

Submission status: Accepted

Solution code:
import numpy as np

[n,m,x] = [int(x) for x in input().split()]
data = np.array([[int(x) for x in input().split()] for _ in range(n)])

ans = []

for i in range(2**(n)):
    temp = np.array([0]*(m+1))

    for j in range(n):
        if (i >> j) & 1:
            temp = temp + data[j]
    
    for k in temp[1:]:
        if k < x:
            break
    else:
        ans.append(temp[0])

if ans == []:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
import sys
import itertools
from typing import Callable, List, NoReturn, Tuple

import numpy as np


def main() -> NoReturn:
    scan: Callable[[], str] = sys.stdin.readline

    n, m, x = map(int, scan().rstrip().split())  # type: int, int, int
    book_matrix: np.ndarray = np.array(
        tuple(
            tuple(int(_1) for _1 in scan().rstrip().split()) for _2 in range(n)
        )
    )

    grasp_matrix = np.split(book_matrix, [1], axis=1)[1]
    max_grasp: np.ndarray = np.sum(grasp_matrix, axis=0)

    if not (max_grasp >= x).all():
        print(-1)
        return

    all_books = tuple(range(n))
    prices: List[int] = []

    for k in range(1, n + 1):
        for combs in itertools.combinations(all_books, k):
            total: np.ndarray = np.zeros(m + 1)
            for book in combs:
                total += book_matrix[book]
            if (total[1:] >= x).all():
                prices.append(total[0])

    print(int(min(prices)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

min_cost = 10**8

for i in range(2**n):
    a = [0] * m
    cost = 0
    for j in range(n):
        if (i >> j) & 1:
            cost += book[j][0]
            for k in range(m):
                a[k] += book[j][k+1]

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

    if valid:
        min_cost = min(min_cost, cost)

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

Submission status: Accepted

Solution code:
import numpy as np

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

C = [0] * N
A = [[0]] * N

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

candidates = []

def iter(i, cost, learned):
    if(all(elm >= X for elm in learned)):
            candidates.append(cost)

    i += 1

    if(i >= N): return 0

    iter(i, cost, learned)
    iter(i, (np.array(cost) + np.array(C[i]).tolist()), (np.array(learned) + np.array(A[i])).tolist())


iter(0, C[0], A[0])
iter(0, 0, [0]*M)

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

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
n, m , x = map(int, input().split())
skill_dic = {} 
for i in range(n):
    tmp = list(map(int, input().split()))
    skill_dic[i] = {'cost':tmp[0],'skills':tmp[1:]}

def calc_cost(skill_books, skill_dic,x):
    skill_nums = len(skill_dic[0]['skills'])
    skills = np.zeros(skill_nums)
    for i in skill_books:
        skills += skill_dic[i]['skills']
    skills = skills.reshape(-1, skill_nums)
    if np.all(skills >= x): return sum([ skill_dic[skill_book]['cost'] for skill_book in skill_books ])
    return None 

i = 1
cost_list = []
while i <= len(skill_dic.keys()):
    book_comb = combinations(skill_dic.keys(),i)
    for pattern in book_comb:
        cost = calc_cost(list(pattern),skill_dic, x)
        if cost is not None: cost_list.append(cost)
    i += 1
print(min(cost_list) if cost_list != [] else -1)

Submission status: Accepted

Solution code:
from itertools import product

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

minimum_cost = float('inf')

buy_selections = product([1, 0], repeat=n)
for selection in buy_selections:
    bought_books = [books[i] for i in range(n) if selection[i]]
    
    total_each = [0] * (m+1)
    for book in bought_books:
        for i in range(m+1):
            total_each[i] += book[i]
    
    if any([total < x for total in total_each[1:]]):
        continue
    if total_each[0] < minimum_cost:
        minimum_cost = total_each[0]

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

Submission status: Accepted

Solution code:
import itertools

N, M, X = list(map(int, input().split()))
C = []
A = []

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

flag_i = False
min_cost = 10**7

for i in range(1, N+1):
    comb_list = list(itertools.combinations(range(N), i))
    
    for comb in comb_list:
        know = [0] * M
        cost = 0
        for book in comb:

            for i in range(M):
                know[i] += A[book][i]
            cost += C[book]
        
        #達成チェック
        flag = True
        for i in range(M):
            if (know[i] < X):
                flag = False
              
        
        if (flag):
            flag_i = True
            
            if (min_cost > cost):
                min_cost = cost
if (flag_i):
    print(min_cost)
    exit(0)

print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import *

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word
tokens = iterate_tokens()
n=int(next(tokens))
m=int(next(tokens))
x=int(next(tokens))
c=[0]*n
a=[[0]*m for _ in range(n)]
for i in range(n):
    c[i]=int(next(tokens))
    for j in range(m):
        a[i][j]=int(next(tokens))

b=[]
def sumb(b):
    ret=0
    for i in range(n):
        if b[i]==1:
            ret+=c[i]
    return ret

def chk_mok(b):
    gak=[0]*m
    for i in range(n):
        if b[i]==1:
            for j in range(m):
                gak[j]+=a[i][j]
    ret=True
    for j in range(m):
        if gak[j]<x:
            ret=False
    return ret

if not chk_mok([1]*n):
    print(-1)
    exit()

ans=sum(c)

def buy(b, i):
    global ans
    if i==n:
        if chk_mok(b):
            ans=min(ans, sumb(b))
    else:
        buy(b+[0], i+1)
        buy(b+[1], i+1)

buy([0], 1)
buy([1], 1)

print(ans)

Submission status: Accepted

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

def all(l):
    for v in l:
        if v<x:
            return False
    return True

D=[[] for _ in range(2**n)]
for x1 in range(2**n):
    w=x1
    for y in range(n):
        D[x1].append(w%2)
        w//=2

for i in range(2**n):
    r=[0]*m
    by=0
    for p in range(n):
        if D[i][p]:

            for j in range(m):
                r[j]+=z[p][1:][j]
            by+=z[p][0]

    if all(r):
        Nedan.append(by)
print(-1 if Nedan==[] else min(Nedan))

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 = [0]*m
costs = []

for i in range(2**n):
    cost = 0
    
    for j in range(n):
        if (i>>j) & 1:
            cost += c[j]
            for k in range(m):
                a[k] += ca[j][k+1]
    
    flag = True
    for l in range(m):
        if a[l] < x:
            flag = False
    if flag:
        costs.append(cost)
    a = [0]*m
if costs == []:
    print(-1)
else:
    print(min(costs))

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(N)]
ans = 10 ** 18
chk = [0] * N

def dfs(next):
    global ans
    if next == N:
        rikai = [0] * M
        total = 0
        ansF = True
        for i in range(N):
            if chk[i] == 1:
                total += ca[i][0]
                for j in range(M):
                    rikai[j] += ca[i][j + 1]

        for i in rikai:
            if i < X:
                ansF = False
                break
        if ansF:
            ans = min(ans, total)
        return

    for i in range(2):
        chk[next] = i
        dfs(next + 1)
    return

dfs(0)

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

Submission status: Accepted

Solution code:
from itertools import combinations


def main():
    N, M, X = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    money = float('inf')

    for i in range(N):
        # print(f"{i=}")
        a = combinations(range(N), i + 1)
        for s in a:
            tmp_money = 0
            rikai = [0] * M
            # print(f"{s=}")
            for x in s:
                # print(f"{x=}")
                tmp_money += A[x][0]
                for m in range(M):
                    rikai[m] += A[x][m + 1]
            # print(f"{rikai=}")
            if min(rikai) >= X:
                money = min(money, tmp_money)
    if money == float('inf'):
        print(-1)
    else:
        print(money)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n,m,X = map(int,input().split())
list_input = []
for x in range(n):
  list_input.append(list(map(int,input().split())))
List = []
List_array = []
for x in list_input:
  List.append(x[0])
  List_array.append(x[1:])
a = np.array(List_array)
List_ans = []
for i in range(2**n):
  s = 0
  t = np.array([0]*m)
  for j in range(n):
    if (i>>j)&1 == 1:
      s += List[j]
      t += a[j]
  if min(t) >= X:
    List_ans.append(s)

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

Submission status: Accepted

Solution code:
import sys

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

a = []
for i in range(n):
  a.append(list(map(int,input().split())))
  
money_min = sys.maxsize
ans = False

for i in range(2 ** n):
  s = bin(i).replace('0b','')
  s = s.zfill(n)
  
  tmp = [0] * (m+1)
  money = 0

  for j in range(len(s)):
    if s[j] == '1':
      money += a[j][0]
      for k in range(1,m+1):
        tmp[k] += a[j][k]
        
  flag = True
  for j in range(1,m+1):
    if tmp[j] < x:
      flag = False
      break
      
  if flag:
    money_min = min(money_min,money)
    ans = True
  
if ans:
  print(money_min)
else:
  print(-1)

Submission status: Accepted

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

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

ans = 10 ** 7
for i in range(1 << N):
    s = [0] * M
    kari = 0
    for j in range(N):
        if (i >> j) % 2 == 1:
            kari += A[j][0]
            for k in range(M):
                s[k] += A[j][k+1]
    if min(s) >= X:
        ans = min(ans, kari)

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

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = list(map(int, input().split()))
a = [list(map(int,input().split())) for l in range(n)]
x_list = [x]*m
s = range(2**n)
ans = 10**10
count = 0
for i in s:
    y = np.zeros(m+1)
    for j in range(n):
        if ((i>>j)&1):
            y = y+np.array(a[j])
    
    if np.all(np.array(y[1:])>=np.array(x_list)):
        count = 1
        ans = min(ans, y[0])  

if count == 1:
    print(int(ans))     
else:
    print(-1)

Submission status: Accepted

Solution code:
import copy
n,m,x=[int(_) for _ in input().split()]
Cmat=[[int(_) for _ in input().split()] for i in range(n)]
lista=[]
money=[]

visited=0
def dfs(lista,visited):
    global x
    global money
    skill=[0]*m
    total=0
    for i,j in enumerate(lista):
        for index,ja in enumerate(Cmat[j]):
            if index==0:
                total+=ja
            else:
                skill[index-1]+=ja
    if lista and all([i>=x for i in skill]):
        #print(total)
        money.append(total)    
    elif visited<n:
        dfs(lista+[visited],visited+1)
        dfs(lista,visited+1)

dfs(lista,visited)
if money:
    print(min(money))
else:
    print(-1)

Submission status: Accepted

Solution code:
inputs = open(0).readlines()
n, m, x = map(int, inputs[0].split())
CA = [list(map(int, x.split())) for x in inputs[1:]]
ans = 10**9
for i in range(2 ** n):
    cost = 0
    B = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            c, *A = CA[j]
            cost += c
            for k in range(m):
                B[k] += A[k]
    if all(b >= x for b in B):
        ans = min(ans, cost)
if ans == 10**9:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
N,M,X = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(N)]
money = [A[i][0] for i in range(N)]
A = [A[i][1:] for i in range(N)]
test = [[A[i][j] for i in range(N)] for j in range(M)]
test = list(map(sum,test))
ans = 0
if min(test) < X:
    ans = -1

if ans == 0:
    from itertools import product
    for cond in product([True,False], repeat=N):
        tmparr = [0] * M
        cost = 0
        for i,j in enumerate(cond):
            if j:
                tmparr = [tmparr[k] + A[i][k] for k in range(M)]
                cost += money[i]
        if min(tmparr) >= X:
            if ans == 0:
                ans = cost
            else:
                ans = min(ans,cost)

print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = []*n
list = [input().split() for l in range(n)]
ans = float('inf')
op_cnt = n
for i in range(2 ** op_cnt):
  flag = 1
  progress =[0]*m
  cost = 0
  op = [0] * op_cnt  # あらかじめ ["-", "-", "-"] というリストを作っておく
  for j in range(op_cnt):
      if ((i >> j) & 1):
          op[op_cnt - 1 - j] = 1
          cost += int(list[op_cnt - 1 - j][0])
          for k in range(m):
            progress[k] += int(list[op_cnt-1-j][k+1])
   
  for l in range(m):
    if progress[l] < x:
      flag = 0
      break
  if flag == 1:
    ans = min(ans,cost)
if ans == float('inf'):
  print(-1)
else:
  print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int, input().split())
texts = []

for i in range(n):
    array = list(map(int, input().split()))
    texts.append(array)
num = 2**n
min_money = 10**20
for i in range(num):
    flg = True
    t = str(format(i, 'b')).zfill(n)
    total = np.zeros(m+1)
    for j in range(n):
        if t[j] == '1':
            total += texts[j]
    y = total[1:]
    for k in y:
        if k < x:
            flg = False
            break
    money = total[0]
    if money < min_money and flg is True:
        min_money = money

if min_money == 10**20:
    print(-1)
else:
    print(int(min_money))

Submission status: Accepted

Solution code:
import numpy as np
import itertools
[N,M,X]=map(int,input().split())
l=[]
for i in range(N):
    
    l.append(list(map(int,input().split())))
l=np.array(l)
num=np.array([i for i in range(N)])
C = l[:,0]
A = l[:,1:]
ans = -1
for i in range(N):
    for c in itertools.combinations(num,i+1):
        score = np.zeros(M)
        cost = 0
        for j in c:
            score=score+A[j]
            cost = cost+C[j]
        if np.min(score)>=X:
            if ans>=cost or ans ==-1:
                ans = cost
if ans ==0:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

Money=0

lst=range(N)
combs = []

for i in range(1, len(lst)+1):
    els = [list(x) for x in itertools.combinations(lst, i)]
    combs.extend(els)

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


Tmp=[0]*(len(combs))

for i in range(len(combs)):
    Skill=[0]*M
    for j in range(len(combs[i])):
        for k in range(M):
            Skill[k]+=inList[combs[i][j]][k+1]
        Tmp[i]+=inList[combs[i][j]][0]

    ok=True
    for k in range(M):
        if(Skill[k]<X):
            ok=False
    if(ok==False):
        Tmp[i]=10000000000

if(min(Tmp)==10000000000):
    print(-1)
else:
    print(min(Tmp))

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int, input().split())
a = []
res = 10000000
for i in range(n):
  a.append(list(map(int, input().split())))
for i in range(1,n+1):
  l = itertools.combinations(range(n),i)
  for j in l:
    tmp = [0]*(m+1)
    for k in j:
      for o in range(m+1):
        tmp[o] += a[k][o]
    flg = 0
    for o in range(1,m+1):
      if tmp[o] < x:
        flg = 1
    if flg == 0:
      res = min(res, tmp[0])
if res == 10000000:
  print(-1)
else:
  print(res)

Submission status: Accepted

Solution code:
import numpy as np
from copy import copy

N, M, X = map(lambda x: int(x), input().split(" "))

Ms = [[0] * (M+1)]
Ms = np.array(Ms)
for _ in range(N):
    n = list(map(lambda x: int(x), input().split(" ")))
    temp_Ms = copy(Ms)
    for m in Ms:
        temp_Ms = np.append(temp_Ms, np.array([m+n]), axis=0)
    Ms = temp_Ms

Cs = Ms[:, 0]
Ms = np.delete(Ms, 0, 1)
result = float("inf")

for i in range(len(Ms)):
    if np.all(Ms[i] >= X):
        result = min(result, Cs[i])

if result == float("inf"):
    result = -1
print(result)

Submission status: Accepted

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

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

minC = 10000000

for i in range(0,pow(2,N),1):
    C = 0
    A = [0 for i in range(0,M+1,1)]
    for j in range(N):
        if((i>>j)&1):
            for k in range(1,M+1,1):
                A[k]+= CA[j][k]
            C += CA[j][0]
    flag = False
    for k in range(1,M+1,1):
        if A[k] < X:
            flag = True
    if flag:
        continue

    if C < minC:
        minC = C

if minC != 10000000:
    print(minC)
else:
    print(-1)

Submission status: Accepted

Solution code:
#coding:utf-8
import queue

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

cost = -1
score = -1
shan = -1

book_c = []
book_a = []
index = [i for i in range(M)]

def judge(c,a):
    m = min(a)
    jud = -1
    if m >= X:
        jud = c
    return jud
    
for i in range(N):
    b = input().split()
    book_c.append(int(b[0]))
    b = b[1:]
    box = []
    for j in b:
        box.append(int(j))
    book_a.append(box)

q = queue.Queue()
q.put('0')
q.put('1')
mak = q.get()
order = len(mak)

while order < N:
    mallo = '0' + mak
    mally = '1' + mak
    q.put(mallo)
    q.put(mally)
    mak = q.get()
    order = len(mak)

q.put(mak)

while not q.empty():
    score = 0
    mak = q.get()
    nas = [int(k) for k in mak]
    anad = [0] * M
    
    for c,kk in zip(book_c,nas):
        score += (c * kk)

    for asa,kk in zip(book_a,nas):
        for ind,kok in enumerate(asa):
            anad[ind] += (kok * kk)

    shan = judge(score,anad)
    if cost == -1:
        cost = shan
    elif shan != -1:
        cost = min(cost,shan)
            

print("{}".format(cost))

Submission status: Accepted

Solution code:
import numpy as np

def python_list_add(in1, in2):
    wrk = np.array(in1) + np.array(in2)
    return wrk.tolist()

n, m, x = map(int,input().split())
li = [list(map(int,input().split())) for i in range(n)]
 #価格の合計
ans = []

for i in range(2 ** n):
    bag = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(j)  # フラグが立っていたら bag に果物を詰める
    
    p = 0
    org = [0]*m
    for k in bag:
        p += li[k][0]
        pos = li[k][1:]
        org = python_list_add(org, pos)
    if all(l >= x for l in org): #条件を満たしていたら
        ans.append(p)


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

Submission status: Accepted

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

price = {}
for i in range(2 ** n):
    rikai = []
    total = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            rikai.append(a[j][1:])  # フラグが立っていたら bag に果物を詰める
            total += a[j][0]  # 買い物累計額にも加算
    price[total] = rikai


# for k,v in price.items():
#     flatv = sum(v, [])
#     for i in range(m):
#         temp += flatv[] #m*iのやつ

def python_list_add(in1, in2):
   return list(map(sum, zip(in1, in2)))

flag = False
minp = (10 ** 5) * 12
for k,v in price.items():
    r = [0]*m
    for i in range(len(v)):
        r = python_list_add(r, v[i])
    if min(r) >= x:
        minp = min(minp, k)
        flag = True

if flag:
    print(minp)
else:
    print("-1")

Submission status: Accepted

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

import itertools
import numpy as np

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

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

# print(data)
ans = 10**6*12
for i in itertools.product([0, 1], repeat=n):
    # print(i)
    data_tmp = np.zeros(m+1, dtype=np.int)
    for index in range(len(i)):
        if i[index] == 0:
            continue
        data_tmp += data[index, :]

    if np.all((data_tmp[1:] >= x)):
        ans = min(ans, data_tmp[0])
        # print(data_tmp)

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections

def solve(N,M,X,C,A):
    lis = [i for i in range(N)]
    ans = []
    for k,_ in enumerate(lis,1):
        for c in itertools.combinations(lis,r=k):
            tmp = 0
            dic = {key:0 for key in range(M)}
            for i in set(c):
                tmp += C[i]
                for n,a in enumerate(A[i]):
                    dic[n] += a
            for m in range(M):
                if(dic[m] < X):
                    break
            else:
                ans.append(tmp)
    return min(ans) if(ans != []) else -1
def main():
    N,M,X = map(int,input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int,input().split()))
        C.append(tmp.pop(0))
        A.append(tmp)
    # solve()
    print(solve(N,M,X,C,A))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

lst=[]
cnt=0
ans=100000000
for _ in range(n):
	a=list(map(int,readline().split()))
	lst.append(a)
	
for i in range(1,2 ** n):
    bag = []
    #print("pattern {}: ".format(i), end="")
    for j in range(n):
      if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行    		
      	bag.append(lst[j])  # フラグが立っていたら bag に果物を詰め
    #print(bag)
    cab=np.array(bag)
    sum=np.sum(cab,axis=0)
    
    cnt=0
    for k in range(m):
    	#print(sum[k+1])
    	if sum[k+1]>=x:
    		cnt+=1
    	if cnt==m:
    		ans=min(ans,sum[0])
    		
if ans==100000000:
	print(-1)
else:
	print(ans)

Submission status: Accepted

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

    for i in range(2 ** N):
        bag = []
        OK = False
        for j in range(N):  
            if ((i >> j) & 1):  
                bag.append(C[j])
        sumlist=[0]*(M+1)
        for j in range(len(bag)):
            for k in range(M+1):
                sumlist[k] += bag[j][k]
        for j in range(M):
            if(sumlist[j+1] < X):
                OK = False
                break
            else:
                OK = True
        if OK and (min==-1 or min > sumlist[0]):
            min = sumlist[0]

    print (min)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
result = float("inf")


def search(subset, depth, costs, x):
    if depth == len(costs):
        local_res = 0
        knowledge = [0] * (len(costs[0]) - 1)
        for i, cost in enumerate(costs):
            if i in subset:
                local_res += cost[0]
                for i, c in enumerate(cost[1:]):
                    knowledge[i] += c
        if done(knowledge, x):
            global result
            result = min(result, local_res)
    else:
        search(subset, depth + 1, costs, x)
        subset.add(depth)
        search(subset, depth + 1, costs, x)
        subset.remove(depth)


def done(knowledge, x):
    for item in knowledge:
        if item < x:
            return False
    return True


def solve(costs, x):
    search(set(), 0, costs, x)

    if result == float("inf"):
        return -1

    return result


if __name__ == "__main__":
    n, m, x = map(int, input().split())
    costs = [[int(x) for x in input().split()] for y in range(n)]
    print(solve(costs, x))