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())
book_list=[list(map(int,input().split())) for _ in range(n)]
ans=-1
for i in range(2**n):
    result=[0]*(m+1)
    for j in range(n):
        if (i>>j)&1:
            for k in range(m+1):
              result[k]+=book_list[j][k]
    if min(result[1:m+1])>=x:
      if ans==-1:
        ans=result[0]
      else:
        ans=min(ans,result[0])
print(ans)

Submission status: Accepted

Solution code:
N, M, X = list(map(int, input().split()))
ca_list = [list(map(int, input().split())) for _ in range(N)]
c = [ca_list[i][0] for i in range(N)]
a = [ca_list[i][1:] for i in range(N)]
ans = sum(c)
check = False

for i in range(2**N):
    total = 0
    skills = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            total += c[j]
            skills = [k + l for k, l in zip(a[j], skills)]
    if all([z >= X for z in skills]):
        ans = min(total, ans)
        check = True

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 29 06:00:56 2020

@author: Aruto Hosaka
"""


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

# C =[[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]]
# N = 8
# M = 5
# X = 10


P = [row[0] for row in C]
A = [row[1:M+1] for row in C]

K = [0 for i in range(2**N)]
G = [[0 for k in range(M)] for i in range(2**N)]
for i in range(2**N):
    i2 = format(i, '012b')
    s = 0
    for k in range(N):
        K[i] += int(i2[11-k])*P[k]
        for j in range(M):
            G[i][j] += int(i2[11-k])*A[k][j]

J = [[K[i],G[i]] for i in range(2**N)]
J = sorted(J)

t = 0
for i in range(2**N):
    for j in range(M):
        if (J[i][1])[j] < X:
            break
        if j == M-1:
            t = 1
            print(J[i][0])
    if t== 1:
        break

if t==0:
    print(-1)

Submission status: Accepted

Solution code:
N , M , X = map(int,input().split())
CA_list = [list(map(int,input().split())) for _ in range(N)]
c = [CA_list[i][0] for i in range(N)]
a = [CA_list[i][1:] for i in range(N)]

cost = sum(c)
ans = 0

#べき乗
for i in range(2**N):
   temp = 0
   skill = [0] * M
   
   for j in range(N):
     if (i >> j) & 1:
        temp += c[j] 
        skill = [y + z for (y,z) in zip(skill,a[j])]
   if all([z >= X for z in skill ]):
        cost= min(cost,temp)
        ans += 1
        
if ans == 0:
    print(-1)
else:
    print(cost)

Submission status: Accepted

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

ans = float('inf')
for bit in range(1 << N):
    book = [0]*M
    cost = 0
    for i in range(N):
        if(bit >> i) & 1:
            cost += CA[i][0]
            for c in range(M):
                book[c] += (CA[i][c+1])
#    print(book)
    if all(X <= a for a in book):
        ans = min(ans,cost)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
A = []
C = []
for _ in range(N):
    c, *a = list(map(int, input().split()))
    A.append(a)
    C.append(c)
ans = float("inf")
for b in range(2**N):
    param = [0]*M
    tmp = 0
    for i in range(N):
        if 1&(b>>i):
            tmp += C[i]
            param = list(map(lambda a,b: a+b, A[i], param))
    if all([x>=X for x in param]):
        ans = min(tmp, ans)
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, M, X = MI()
    C = []
    A = []
    for i in range(N):
        tmp = LI()
        C.append(tmp[0])
        A.append(np.array(tmp[1:]))

    ans = INF
    for i in range(1 << N):
        bag = []
        for j in range(N):
            if (i >> j) & 1:
                bag.append(j)
        sm = np.zeros(M)
        c = 0
        for b in bag:
            c = c + C[b]
            a = A[b]
            sm = sm + a
        if np.all(sm >= X):
            ans = min(ans, c)

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





if __name__ == '__main__':
    solve()

Submission status: Accepted

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

INF = 10 ** 9
ans = INF

for s in range(0, 1 << n):
  smart = [0] * m
  cost_sum = 0

  for i in range(n):
    if (s >> i) % 2 == 0:
      continue
    cost_sum += c[i]

    for j in range(m):
      smart[j] += a[i][j]

    ok = True
    for j in range(m):
      if smart[j] < x:
        ok = False
    if ok:
      ans = min(ans, cost_sum)

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

Submission status: Accepted

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

for mask in range(2 ** n):
    C = [0] * m
    cost = 0

    for i in range(n):
        if (mask >> i) & 1:
            cost += X[i][0]
            #値段を加味して1から始めてる。そして収得すべきアルゴリズムの個数m
            #n個本があるので二次元配列のひとつめはi, m冊本があるので第2引数はj
            #Cはフラグの個数。

            for j in range(1, m + 1):
                C[j - 1] += X[i][j]
    #こいつ天才か?下一個舐めれば理解できるもんな。
    if min(C) >= x:
        ans = min(ans, cost)

if ans < 91912922191:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int, input().split())
C, A = [], []
for i in range(n):
	c, *a = map(int, input().split())
	C.append(c)
	A.append(a)
# print(A)
# print(C)
cost=0
#preserve each sums of algorithms
# print(X)
flg=False
ans=sum(C)
for i in range(1,2**n):
	# X=[[0] for _ in range(m)]
	X=[0]*m
	cost=0
	flg=True
	#j is the chosen textbook
	for j in range(n):
		if (i>>j)&1 == 1:
			cost += C[j]
			for k in range(m):
				X[k] += A[j][k]
	for idx in X:
		if idx < x:
			flg = False
			break
	# print(X)
	# print("C[]: ", C)
	# print("cost: ", cost)
	# print("ans: ", ans)
	if flg:
		ans = min(ans,cost)

if flg:
	print(ans)
else:
	print('-1')

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

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

A = np.array(A)
C = np.array(C)

answer = 10**9
for comb in itertools.product([0, 1], repeat= N):
    cost = 0
    A_memo = np.zeros(M, dtype=int)

    for i in range(N):
        if not comb[i]:
            continue

        A_memo += A[i]
        cost += C[i]

    if (A_memo >= X).sum() == M:
        answer = min(answer, cost)

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

Submission status: Accepted

Solution code:
def solve():
    N,M,X = map(int,input().split())
    C = []
    A = []
    for _ in range(N):
        CA = list(map(int,input().split()))
        C.append(CA[0])
        A.append(CA[1:])
    
    ans = float('inf')
    for i in range(1<<N):
        cost_sum = 0
        power = [0] * M
        for j in range(N):
            if (i >> j) & 1:
                cost_sum += C[j]
                for k in range(M):
                    power[k] += A[j][k]
        
        isOk = True
        for j in range(M):
            if power[j] < X:
                isOk = False
                break
        
        if isOk:
            ans = min(ans, cost_sum)
    
    print(ans if ans != float('inf') else -1)
        
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

minprice = 1<<34
canComp = False
for i in itertools.product([0, 1], repeat=N):
    ok = True
    known = [0] * M
    price = 0
    for n, j in enumerate(i):
        if j == 1:
            book = books[n]
            price += book[0]
            for a, know in enumerate(book[1:]):
                known[a] += know

    for know in known:
        if know < X:
            ok = False
            break
    if ok:
        canComp = True
        minprice = min(minprice, price)
    
if canComp:
    print(minprice)
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C_fix
# CreatedDate:  2020-06-27 14:37:15 +0900
# LastModified: 2020-06-27 15:25:50 +0900
#


import os
import sys
from itertools import combinations
import numpy as np
# import pandas as pd


def main():
    n, m, x = map(int, input().split())
    s = []
    for i in range(n):
        s.append(list(map(int, input().split())))
    s = np.array(s)
    total = 100000000


    for i in range(1, n+1):
        for lili in list(combinations(range(n), i)):
            s_list = np.zeros((m+1), dtype=np.int32)
            for li in lili:
                s_list += s[li]

            if (s_list[1:] >= x).all() and s_list[0] < total:
                total = s_list[0]
    if total == 100000000:
        print(-1)
    else:
        print(total)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
p = float("inf")

for i in range(1, 2 ** n):
    s = [0] * m
    count = 0
    ps = 0
    for j in range(n):
        if (i >> j) & 1:
            ps += a[j][0]
            for k in range(m):
                s[k] += a[j][k + 1]

    for k in range(m):
        if s[k] >= x:
            count += 1

    if count == m:
        p = min(ps, p)

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

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
from itertools import combinations as combination
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))

def subset(A):
    for l in range(len(A) + 1):
        for comb in combination(A, l):
            yield comb

def solve():
    n, m, x = rl()
    C = []
    A = []
    for i in range(n):
        line = rl()
        C.append(line[0])
        A.append(line[1:])

    min_cost = 10**20
    for sub in subset(range(n)):
        skills = [0] * m
        cost = 0
        for s in sub:
            for i in range(m):
                skills[i] += A[s][i]
            cost += C[s]

        for skill in skills:
            if skill < x:
                break
        else:
            min_cost = min(min_cost, cost)

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






mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
p = float("inf")

for i in range(1, 2**n):
    s = [0]*m
    count = 0
    ps = 0
    for j in range(n):
        if (i >> j) & 1:
            ps += a[j][0]
            for k in range(m):
                s[k] += a[j][k+1]
                
    for k in range(m):
        if s[k] >= x:
            count += 1
            
    if count == m:
        p = min(ps, p)
        
if p == float('inf'):
    print(-1)
else:
    print(p)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
C=[[] for i in range(n)]
for i in range(n):
  A=list(map(int,input().split()))
  C[i]=[A[0],A[1:]]
  
  
cost=float("inf")
for bit in range(1<<n):
  #print([j for j in range(n) if bit>>j & 1 ])
  for i in range(m):
    if sum([C[j][1][i] for j in range(n) if bit>>j & 1 ])<x:
      break
  else:
    cost=min(cost, sum([C[j][0] for j in range(n) if bit>>j & 1 ]))
    #print(cost)
print(cost if cost<float("inf") else -1)

Submission status: Accepted

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

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

ans = 10**7
for bit in range(1<<n):
    cost = 0
    ex = [0] * m
    for i in range(n):
        if bit & (1<<i):
            cost += c[i]
            for j in range(m):
                ex[j] += a[i][j]

    f = True
    for i in range(m):
        if ex[i] < x:
            f = False
            break
    if f:
        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())
c = [0] * n
a = [[0] * m for _ in range(n)]
for i in range(n):
    c[i], *a[i] = map(int, input().split())

ans = float("inf")
for i in range(1<<n):
    t = [0] * m
    cost = 0
    for j in range(n):
        if i & (1<<j):
            cost += c[j]
            for k in range(m):
                t[k] += a[j][k]
    if min(t) >= x:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
*o, = open(0)

import numpy as np

(n, m, x), *ca = map(lambda x: np.array(list(map(int, x.split()))), o)

INF = 1 << 31

ans = INF

for i in range(2**n):
    tmp = np.zeros(m+1, int)
    sel = []
    for j, dig in enumerate(bin(i)[2:][::-1]):
        if int(dig):
            tmp += ca[j]
            sel.append(j)
    if min(tmp[1:]) >= x:
        ans = min(ans, tmp[0])
        

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

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, chain
from operator import itemgetter
from functools import reduce

n, m, x = map(int, next(sys.stdin).split())
books = [tuple(map(int, s.split())) for s in sys.stdin]

book_combinations = chain.from_iterable(combinations(books, i)
                                        # because X >= 1
                                        # for i in range(n + 1))
                                        for i in range(1, n + 1))

def total_price(book_list, _price_getter=itemgetter(0)):
  return sum(map(_price_getter, book_list))
def min_score(book_list, _score_getter=itemgetter(slice(1, None))):
  book_scores = map(_score_getter, book_list)
  scores = [0] * m
  for book_score in book_scores:
    for i, score in enumerate(book_score):
      scores[i] += score
  return min(scores)

price_score_list = ((total_price(book_list), min_score(book_list))
                    for book_list in book_combinations)
prices = (price for price, score in price_score_list if score >= x)
answer = min(prices, default=-1)
print(answer)

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 9999999999
for i in range(2 ** n):
    p = np.zeros(m)
    csum = 0
    for j in range(n):
        if i & (2 ** j):
            p += a[j]
            csum += c[j]
    if np.amin(p) >= x and csum < ans:
        ans = csum
if ans == 9999999999:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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
  
def check(learn_total):
  for i in range(m):
    if learn_total[i] < x:
      return False
  return True
    
for i in range(n):
  c_temp, *a_temp = list(map(int, input().split()))
  c.append(c_temp)
  a.append(a_temp)
  
INF = float("inf")
ans = INF

for bit in range(1 << n):
  price = calc_price(bit)
  ans = min(ans, price)
  
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/abc167/submissions/13218188

MAX = 100000000000
def resolve():
    N,M,X = map(int,input().split())
    A,C = [],[]
    for _ in range(N):
        c_a = list(map(int, input().split()))
        c = c_a.pop(0)
        A.append(c_a)
        C.append(c)
    
    def func(cost,a,i):
        if min(a) >= X:
            return cost
        elif i == N:
            return MAX
        total_A = [x+y for (x,y) in zip(a,A[i])]
        
        return min(func(cost + C[i],total_A,i+1),func(cost,a,i+1))

    ans = func(0,[0]*M,0) 
    if ans == MAX:
        print(-1)
    else:
        print(ans)
resolve()

Submission status: Accepted

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

ans = float("inf")
for i in range(2**n):
    tmp = 0
    A = [0] * m
    for j in range(n):
        if i & 2**j:
            tmp += BOOKS[j][0]
            for k in range(m):
                A[k] += BOOKS[j][k + 1]
    flag = True
    for a in A:
        if a < x:
            flag = False
    if flag:
        ans = min(ans, tmp)

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

Submission status: Accepted

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

ans = []
for i in range(1, 2**N):
    tmp = []
    pnt = 0
    for j in range(N):
        if i>>j & 1 == 1:
            tmp.append(A[j])
            pnt += C[j]
    *score, = map(sum, zip(*tmp))
    if min(score) >= X:
        ans.append(pnt)

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

Submission status: Accepted

Solution code:
import sys

# n:参考書の数
# m:アルゴリズム数
# x:目標の理解度
# arr[0]:C円, …理解度UP値
n, m, x = map(int, input().split())
arr = []
for i in range(n):
    c = list(map(int, input().split()))
    arr.append(c)

# 最小コストを求める
ret = sys.maxsize
for i in range(2**n):
    _cost = 0
    _know = [0] * m
    for j in range(n):
        if i & (1 << j):
            for k in range(m):
                _know[k] += arr[j][1+k]
            _cost += arr[j][0]

    # 目標に達しているかチェック
    flag = True
    for j in range(m):
        if _know[j] < x:
            flag = False
            break

    if flag and ret > _cost:
        ret = _cost

if ret == sys.maxsize:
    ret = -1

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

Submission status: Accepted

Solution code:
from itertools import product
n,m,x = map(int,input().split())
books = [list(map(int,input().split())) for i in range(n)]
costs = []
skills = []
for book in books:
    costs.append(book[0])
    skills.append(book[1:])

ans = float('inf')

for bit in product((0,1),repeat=n):
    #print('bit',bit)
    current_cost = 0
    current_skill = [0] * m
    for i in range(n):
        if bit[i] == 1:
            for j in range(m):
                current_skill[j] += skills[i][j]
                #print('current_s',current_skill[j])
            current_cost += costs[i]


    if x <= min(current_skill):
        ans = min(ans,current_cost)


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

Submission status: Accepted

Solution code:
import numpy as np
import sys
n,m,x = map(int,input().split())
input_list = [np.array(list(map(int,input().split()))) for _ in range(n)]
temp_fee = sys.maxsize
for i in range(2**n):
    list2 = [np.array([0]*(m+1))]
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(input_list[j])
    list3 = sum(list2)
    if min(list3[1:])>=x and list3[0]<temp_fee:
        temp_fee = list3[0]
if temp_fee != sys.maxsize:
    print(temp_fee)
else:
    print(-1)

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()))
  c = []
  a = [] 

  for i in range(n):
    c_temp, *a_temp = list(map(int, input().split()))
    c.append(c_temp)
    a.append(a_temp)

  INF = float("inf")
  ans = INF

  for bit in range(1 << n):
    price = calc_price(bit)
    ans = min(ans, price) 

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

Submission status: Accepted

Solution code:
from collections import deque

n, m, x = map(int, input().split())
c = deque()
a = deque()
ans = float("inf")

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

for i in range(2**n):
    t = 0
    score = [0]*m
    for j in range(n):
        if i&(2**j) > 0:
            t += c[j]
            for k in range(m):
                score[k] += a[j][k]
    if min(score) >= x:
        ans = min(ans, t)

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

Submission status: Accepted

Solution code:
n, m, x = list(map(int, input().split()))
c = [0] * n
a = [[]  for _ in range(n)]
INF = float('inf')
ans = INF

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

for s in range(1<<n):
    smart = [0] * m
    cost = 0
    for i in range(n):
        if not(s>>i & 1):continue
        cost += c[i]
        for j in range(m):
            smart[j] += a[i][j]

    flg = True
    for i in range(m):
        if smart[i] < x:
            flg = False
    if flg:
        ans = min(ans, cost)
if ans == INF:
    print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(100000)

def dfs(cost, i, ratio):
    if i == n:
        global ans
        if cost < ans and all([r >= x for r in ratio]):
            ans = cost
        return
    dfs(cost, i+1, ratio)
    dfs(cost+c[i], i+1, ratio+a[i])

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    c = [None]*n
    a = np.array([None]*n)
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    ans = 10**8
    dfs(0, 0, np.array([0]*m))
    if ans == 10**8:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n,m,x=[int(i) for i in input().split()]
a=[]
for i in range(n):
    a.append([int(i) for i in input().split()])
cost=[]
for i in range(1,n+1):
    c=list(combinations(a,i))
    b=[[0]*(m+1) for i in range(len(c))]
    for k in range(len(c)):
        for j in range(len(c[k])):
            for i in range(m+1):
                b[k][i]+=c[k][j][i]
    for i in range(len(b)):
        s=0 ; flag=0
        for j in range(1,len(b[i])):
            if b[i][j]<x:
                flag=1
                break
        if flag==0: 
            cost.append(b[i][0])
if not cost: print(-1)
else: print(min(cost))

Submission status: Accepted

Solution code:
from itertools import product

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:]) # コストと勉強分を分けて管理
# L = [list(map(int, input().split())) for _ in range(N)]

ans = 10**9

for bit in product((0, 1), repeat=N):
    cost = 0
    study = [0] * M
    for i in range(N):
        if bit[i]:
            for m in range(M):
                study[m] += A[i][m]
            cost += C[i]

    if min(study) >= X: # 最小値が基準より大きければよい
        ans = min(ans, cost)

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

Submission status: Accepted

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

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

mincost = 10e9
ok = False
for i in range(1 << N):
    cost = 0
    skill = [0] * M

    for u in range(N):
        if i & (1<<u):
            cost += C[u]
            for si, s in enumerate(A[u]):
                skill[si] += s
    
    # check
    if all([s >= X for s in skill]):
        ok = True
        if mincost > cost:
            mincost = cost

print(mincost if ok else -1)

Submission status: Accepted

Solution code:
import itertools

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

c = []
a = []
calc = [0] * m


for cai in ca:
  tmp = list(map(int,cai.split()))
  c.append(tmp[0])
  a.append(tmp[1:])

ite = itertools.product(range(2), repeat=n)
ans = float('inf')
tmp = 0
k = 0
for i in ite:
  calc = [0] * m
  tmp = 0
  for j in range(n):
    if i[j] == 1 :
      tmp += c[j]
      for k in range(m):
        calc[k] += a[j][k] 
  if len([z for z in calc if z >= x]) == m:
    ans = min(ans,tmp)

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

Submission status: Accepted

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

ans = 10**9
for i in range(1, n+1):
  for j in combinations(ca, i):
    t = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        t[l] += k[l]
    if all(t[q] >= x for q in range(1,m+1)):
      ans = min(ans, t[0])
if ans != 10**9: print(ans)
else: print(-1)

Submission status: Accepted

Solution code:
n, m, x=map(int, input().split())
c=[]
a=[]
for i in range(n):
  l=list(map(int, input().split()))
  c.append(l[0])
  a.append(l[1:])
import numpy as np
ab=np.array(a).T

ans=[]
#print(c)
#print(ab)
from itertools import product
s = [0,1]
for i in sorted(list(product(s, repeat=n))):
  for t in ab:
    if sum(np.array(t)*np.array(i))<x:
      break
  else:
    ans.append(sum(np.array(i)*np.array(c)))
    continue
if ans==[]:
  print(-1)
else:
  print(min(ans))

Submission status: Accepted

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

nums = []

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

ans = 10000000000


for i in range(2**N):

    money = 0
    skill_point = [0]*M
    goal = [0]*M
    buy = []

    for k in range(N):
        if i>>k & 1:
            buy.append(nums[k])

    for d in buy:
        money += d[0]
        for e in range(M):
            skill_point[e] += d[e+1]

    for f in range(M):
        if skill_point[f] >= X:
            goal[f] = 1

    
    if (0 not in goal) and (money < ans) :
        ans = money

    

if ans != 10000000000:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

nums = []

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

ans = 10000000000


for i in range(2**N):

    money = 0
    skill_point = [0]*M
    goal = [0]*M
    buy = []
    

    for k in range(N):
        if i>>k & 1:
            buy.append(nums[k])

    for d in buy:
        money += d[0]
        for e in range(M):
            skill_point[e] += d[e+1]

    for f in range(M):
        if skill_point[f] >= X:
            goal[f] = 1

    
    if (0 not in goal) and (money < ans) :
        ans = money

    

if ans != 10000000000:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
#bit全探索を用いて全組み合わせを列挙していく

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

INF = 100000000001
ans = INF

for i in range(2**n):
    price = 0
    level = [0]*m
    for j in range(n):
        if  ((i >> j) & 1):
            for k in range(m):
                level[k] += a[j][k]
            price += c[j]
    if min(level) >= x and price <= ans:
        ans = price

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

Submission status: Accepted

Solution code:
import numpy as np

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

for _ in range(n):
  tmp = list(map(int, input().split()))
  matrix.append(tmp)

list_ = []
for i in range(2**n):
  check_list = [0 for _ in range(n)]
  cnt=0
  while True:
    check_list[cnt] = i%2
    i //= 2
    cnt+=1
    if i==0:
      break
  list_.append(check_list)

ans = 100000000000000
for check in list_:
  ans_list = np.zeros(m+1)
  for i, v in enumerate(check):
    if v==1:
      ans_list += np.array(matrix[i])


  flg = True
  for value in ans_list[1:]:
    if value<x:
      flg=False
  if flg:
    ans = min(ans,ans_list[0])

if ans == 100000000000000:
  ans = -1
print(int(ans))

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,m,x=nii()
l=[lnii() for i in range(n)]

ans=10**9
for i in range(2**n):
  ml=[0 for j in range(m)]
  use=[0 for i in range(n)]

  for j in range(n):
    if (i>>j)&1:
      use[j]=1

  t_ans=0
  for j in range(n):
    if use[j]==1:
      use_book=l[j]
      t_ans+=use_book[0]
      for k in range(1,m+1):
        ml[k-1]+=use_book[k]

  if min(ml)>=x:
    ans=min(ans,t_ans)

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