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())
data = [list(map(int,input().split())) for i in range(N)]

A = []
for i in range(2**N):
    B = [0]*M
    price = 0
    for j in range(N):
        if i >> j & 1:
            price += data[j][0]
            for k in range(M):
                B[k] += data[j][k+1]
    for j in range(M):
        if B[j] < X:
            break
    else:
        A.append(price)
if len(A) == 0:
    print(-1)
else:
    print(min(A))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))


def main():
    min_money = float('inf')

    N,M,X = MAP()
    A = [LI() for _ in range(N)]

    from itertools import product

    for bit in product([0,1],repeat=N):
        ability = [0]*M
        money = 0

        for i in range(N):
            if bit[i] == 1:
                money += A[i][0]
                
                for j in range(M):
                    ability[j] += A[i][j+1]

        for aa in ability:
            if aa >= X:
                continue
            else:
                break
        else:
            min_money = min(min_money,money)
         
    if min_money == float('inf'):
        print(-1)
    else:
        print(min_money)
    
    return 




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M, X = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    ans=10**7
    for i in range(2**12):
        count=0
        und=[0]*M
        for n in range(N):
            if i >>n &1:
                s=S[n]
                count+=s[0]
                for j in range(M):
                    und[j]+=s[j+1]
        flag=True
        for j in range(M):
            if und[j]<X: 
                flag=False
                break
        if flag:
            ans=min(ans,count)
            
    if ans ==10**7:
        print(-1)
    else:
        print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, m, x = inpl()
data = [inpl() for _ in range(n)]
ans=INF
for t in itertools.product([0, 1], repeat=n):
    tmp = 0
    a=[0]*m
    for idx, use in enumerate(t):
        if not use:
            continue
        else:
            tmp+=data[idx][0]
        for i in range(m):
            a[i] += data[idx][i + 1]
    FLAG=True
    for i in range(m):
        if a[i] < x:
            FLAG = False
            break
    if FLAG:
        ans=min(ans,tmp)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys, os

def f():
    args = list(map(int,input().split()))
    if len(args) > 1:
        return args
    return args[0]

if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n,m,x = f()
    data = []
    for i in range(n):
        data.append(f())
    
    ans = 10**8
    for i in range(1<<n):
        cursummoney = 0
        curleve = [0] * m
        for j in range(n):
            if i&(1<<j):
                cursummoney += data[j][0]
                for k in range(m):
                    curleve[k] += data[j][1+k]
        ok = 1
        for j in range(m):
            if curleve[j] < x:
                ok = 0
        
        if ok:
            ans = min(ans, cursummoney)
    
    if  ans != 10**8:
        print(ans)
    else:
        print(-1)
    



solve()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
books = [input().split() for i in range(N)]
min_costs = float('inf')

for i in range(2 ** N):
    tmp_costs = 0
    skills = [0 for i in range(M)]
    for j in range(N): 
        if ((i >> j) & 1):
            tmp_costs += int(books[j][0])
            for k in range(M):
                skills[k] += int(books[j][k+1])
    
    if len([i for i in skills if i >= X]) == M:
        min_costs = min(min_costs, tmp_costs)

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

Submission status: Accepted

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

for x in range(2**N):
    indexes = [n for n in range(N) if (x >> n) % 2]
    if X <= min([sum([RB[i][j] for i in indexes]) for j in range(1, M+1)]):
        temp = sum([RB[i][0] for i in indexes])
        if ans > temp:
            ans = temp

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

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
k=[list(map(int,input().split())) for i in [0]*n]
l=12*10**5+1
a=list(range(n))
for i in range(1,n+1):
    for v in itertools.combinations(a,i):
        s=0
        p=[0]*m
        for j in v:
            q=k[j]
            s+=q[0]
            for b in range(m):
                p[b]+=q[b+1]
        t=1
        for j in p:
            if j<x:
                t=0
        if t:
            l=min([s,l])
print(l) if l<12*10**5+1 else print(-1)

Submission status: Accepted

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

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    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:])
    INF = 10**10
    minCost = INF
    for b in range(1<<N):
        cost = 0
        costs = [0] * M
        for j in range(N):
            if b & 1 > 0:
                for k in range(M):
                    costs[k] += A[j][k]
                cost += C[j]
            b= b>>1
        if min(costs) >= X:
            minCost = min(minCost,cost)
    if minCost == INF:
        print(-1)
    else:
        print(minCost)


    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

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)

INF = 10**10
answer = INF
L = list(range(N))
for n in range(1,N+1):
    for comb in combinations(L, n):
        cost = 0
        S = [0]*M
        for i in comb:
            cost += C[i]
            for m in range(M):
                S[m] += A[i][m]
        if all(s >= X for s in S):
            answer = min(answer, cost)

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

Submission status: Accepted

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

INF = 10**10
ans = INF
for x in range(1<<N):
    cost=0
    R=[0]*M
    for i in range(N):
        if (x>>i)&1: continue
        cost+=C[i]
        for m,a in enumerate(A[i]):
            R[m]+=a

    if min(R)>=X:
        ans=min(ans,cost)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

n,m,x = l_in()

MAX = 10000000
res = MAX


C = []
A = []
for _ in range(n):
    tmp = l_in()
    c = tmp[0]
    a = tmp[1:]
    C.append(c)
    A.append(a)

stack = []

def evaluate():
    R = [0]*m
    c = 0
    for i, t in enumerate(stack):
        if t == 1:
            c += C[i]
            for j, b in enumerate(A[i]):
                R[j] += b

    if all(r >= x for r in R):
        return c
    else:
        return MAX
            

def do(i):
    tmp = MAX
    for t in [0,1]:        
        stack.append(t)
        if i == n-1:
            tmp = min(tmp, evaluate())
        else:
            tmp = min(tmp, do(i+1))
        stack.pop()
    return tmp

res = do(0)
    
if res == MAX:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:

def main():
    N, M, X = map(int, input().split())
    A = [[] for _ in range(N)]
    C = []
    for i in range(N):
        x = input().split()
        C.append(int(x[0]))
        A[i] = list(map(int, x[1:]))
    mn = 1e12 
    for i in range(1<<N):
        K = [0 for _ in range(M)]
        c = 0
        for j in range(N):
            if i>>j & 1:
                K = [x+y for (x, y) in zip(K, A[j])]
                c += C[j]
        if all([k >= X for k in K]):
            mn = min(mn, c)
    if mn > 1e10:
        print("-1")
    else:
        print(mn)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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

ans = 10**7
for buy in product(range(2),repeat = n):
    
    buy = np.array(buy)
    judge = (np.dot(buy,ca[:,1:]) >= x).all()
    if judge:
        ans = min(ans, np.dot(ca[:,0],buy))
    
if ans == 10**7: 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)]
ans = float("INF")
for i in range(2**n):
    d = [(i >> j) & 1 for j in range(n)]
    res = [0] * m
    ans_ = 0
    flag = True
    for i in range(n):
        if d[i]:
            ans_ += ca[i][0] 
            for j in range(1, m+1):
                res[j-1] += ca[i][j]
    for k in res:
        if k < x:
            flag = False
            break
    if flag: ans = min(ans, ans_)
if ans == float("INF"): print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8


def main():
    N, M, X = map(int, input().split())
    C = [None] * N
    A = [None] * N

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

    min_moneys = []

    def rec(i, scores, money, X):
        if i == N:
            if all([score >= X for score in scores]):
                min_moneys.append(money)
            else:
                return None

        if all([score >= X for score in scores]):
            min_moneys.append(money)
            return None

        rec(i+1, scores, money, X)
        rec(i+1, [scores[j]+A[i][j] for j in range(M)], money+C[i], X)

    rec(0, [0] * M, 0, X)
    
    if len(min_moneys) == 0:
        return -1

    return min(min_moneys)



print(main())

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
costs = []
incs = []
for _ in range(N):
    C, *inc = map(int, input().split())
    costs.append(C)
    incs.append(inc)
ans = 1e100
for i in range(1 << N):
    tot = 0
    skills = [0] * M
    for j in range(N):
        if (i & (1 << j)) == 0:
            continue
        tot += costs[j]
        for k in range(M):
            skills[k] += incs[j][k]
    if min(skills) >= X:
        ans = min(ans, tot)
if ans == 1e100:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    n, m, x = LI()
    C = []
    A = [[] for _ in range(n)]
    money = inf
    for i in range(n):
        inp = LI()
        C.append(inp[0])
        A[i] = inp[1:]
    for i in range(1 << n):
        rikai = [0] * m
        flag = True
        kingaku = 0
        for j in range(n):
            if (i >> j) & 1 == 1:
                for k in range(m):
                    rikai[k] += A[j][k]
                kingaku += C[j]
        for r in rikai:
            if r < x:
                flag = False
        if flag:
            money = min(money, kingaku)
    if money != inf:
        print(money)
    else:
        print("-1")
main()

Submission status: Accepted

Solution code:

import collections


def solve(n, m, x, bookPrices, bookKnowledge):
    def go(i, achievedKnowledge):
        allHigherThanX = True

        for j in range(m):
            if achievedKnowledge[j] < x:
                allHigherThanX = False
                break

        if allHigherThanX:
            return 0

        if i >= n:
            return float("inf")

        newKnowledge = [achievedKnowledge[j] + bookKnowledge[i][j]
                        for j in range(m)]
        ans1 = bookPrices[i]

        return min(ans1 + go(i+1, newKnowledge), go(i+1, achievedKnowledge))

    ans = go(0, [0 for _ in range(m)])

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


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

bookPrices = []
bookKnowledge = []

for i in range(n):
    arr = list(map(int, input().strip().split()))
    bookPrices.append(arr[0])
    bookKnowledge.append(arr[1:])


print(solve(n, m, x, bookPrices, bookKnowledge))

Submission status: Accepted

Solution code:
#n=int(input())
n,m,X=map(int,input().split())
C=[]
A=[]

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

ans = 10**9
for x in range(2**n):
    v=[0 for _ in range(m)]
    p=x
    c=0
    for i in range(n):
        if p%2==1:
            c+=C[i]
            for j in range(m):
                v[j] += A[i][j]
        p//=2
    f=True
    for j in range(m):
        if v[j]<X:
            f = False
            break
    if f:
        ans = min(ans, c)

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

Submission status: Accepted

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

ans = float('inf')
for i in range(2**N):
    rikai = [0]*M
    onedan = 0
    for j in range(N):
        if (i>>j) & 1:
            onedan += books[j][0]
            for k in range(1,M+1):
                rikai[k-1] += books[j][k]
    for r in rikai:
        if r < X:
            break
    else:
        ans = min(ans,onedan)

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

Submission status: Accepted

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

ans=10**20
from itertools import *
for tmp in list(product([True,False], repeat=n)):
    cost=0
    algo = [0] * m
    for i in range(n):
        if tmp[i]:
            cost+=ca[i][0]
            for j in range(m):
                algo[j] += ca[i][j+1]

    ok=True
    for i in range(m):
        if algo[i] < x:
            ok=False
    if ok:
        ans=min(ans,cost)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
lis = []
for i in range(n):
    lis.append(list(map(int, input().split())))
r = []    
for i in range(2**n+1):
    num = i
    a = [0 for _ in range(m)]
    p = 0
    for j in range(n):
        if num%2==1:
            p += lis[j][0]
            for s in range(m):
                a[s] += lis[j][s+1]
        num >>= 1
    if all(i>=x for i in a):
        r.append(p)
if len(r)==0:
    print(-1)
else:
    print(min(r))

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
A = []
INF = 1e18
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
ans = INF
for S in range((1<<N)):
    cost = 0
    unst = [0 for i in range(M)]
    for i in range(N):
        if S & (1<<i):
            cost += A[i][0]
            for j in range(M):
                unst[j] += A[i][j+1]
    flag = 1
    for i in range(M):
        if unst[i] < X:
            flag = 0
            break
    if flag:
        if ans > cost:
            ans = cost
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M,X = map(int,input().split())
CA = [list(map(int,input().split())) for _ in range(N)]
MIN = 10**7
for i in range(2**N):
    ler = [0]*M
    money = 0
    bitlist = deque()
    for j in range(N):
        if ((i >> j) & 1): #2進数表示のj桁目(0桁目から数える)が1かどうか
            bitlist.appendleft(1)
        else:
          	bitlist.appendleft(0)
    bitlist = list(bitlist)
    for k in range(N):
        if bitlist[k] == 1:
            money += CA[k][0]
            for l in range(1,M+1):
                ll = CA[k][l]
                ler[l-1] += ll
    judge = 0
    for ju in range(M):
        if ler[ju] < X:
            judge = 1
            break
    if judge == 0:
        MIN = min(MIN,money)
if MIN == 10**7:
    print(-1)
else:
    print(MIN)

Submission status: Accepted

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

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

ans=10**9
for i in range(2**n):
    s = str(bin(i))
    s = s[2:]
    s = "0"*(n-len(s))+s

    flag=True
    tmp=0
    p = [0]*m
    for j in range(n):
        if s[j]=="0":
            continue
        tmp+=l[j][0]
        for k in range(m):
            p[k]+=l[j][k+1]
    for j in p:
        if j<x:
            flag = False
            break
    if flag:
        ans = min(tmp,ans)

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

Submission status: Accepted

Solution code:
import itertools


n, m, x = map(int, input().split())
book_costs = list()
book_skills = list()
for i in range(n):
    line = list(map(int, input().split()))
    book_cost = line[0]
    book_skill = line[1:]
    book_costs.append(book_cost)
    book_skills.append(book_skill)
    

ans = 12 * 101001
for flags in itertools.product(*[[True, False]] * n):
    cost = 0
    skill = [0 for i in range(m)]
    for i, flag in enumerate(flags):
        if flag:
            cost += book_costs[i]
            for j, skl in enumerate(book_skills[i]):
                skill[j] += skl
    
    if min(skill) >= x:
        ans = min(ans, cost)

if ans == 12 * 101001:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')
# ----------------------------------------------------------- #

n, m, x = Is()
CA = LIR(n)

ans = INF
for bit in range(1<<n):
    B = [0]*m
    money = 0
    for i in range(n):
       if bit & (1<<i):
           money += CA[i][0]
           for j in range(m):
               B[j] += CA[i][j+1]
    for j in range(m):
        if B[j] < x:
            break
    else:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
from itertools import combinations
def main():
    N, M, X = map(int, input().split())
    l = []
    for _ in range(N):
        A = list(map(int, input().split()))
        l.append(A)
    m = pow(10, 7)
    for i in range(1, N+1):
        for j in combinations([k for k in range(N)], i):
            ll = [0] * (M+1)
            for k in j:
                for w in range(M+1):
                    ll[w] += l[k][w]
            if min(ll[1:]) >= X:
                m = min(m, ll[0])
    if m >= pow(10, 7):
        return -1
    return m

print(main())

Submission status: Accepted

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

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

a = 10000000000
for v in range(2 ** N):
    tv, tk = 0, [0 for _ in range(M)]
    for i in range(N):
        if v & (1 << i) != 0:
            tv += L[i][0]
            for p in range(M):
                tk[p] += L[i][p + 1]

    f = True
    for p in range(M):
        if tk[p] < X:
            f = False
            break

    if f:
        a = min(a, tv)

if a == 10000000000:
    print(-1)
else:
    print(a)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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

for _ in range(n):
    c, *a = map(int, input().split())
    cost.append(c)
    aaa.append(a)

cost = np.array(cost, dtype=np.int64)
aaa = np.array(aaa, dtype=np.int64)

ans = 10 ** 18
for books in product([True, False], repeat=n):
    books = list(books)
    if (aaa[books].sum(axis=0) >= x).all():
        ans = min(ans, cost[books].sum())
if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

cost=10**10
for i in range(2**n):
    rikai=[0]*m
    tmp=0
    for j in range(n):
        if (i>>j)%2==1:
            tmp+=C[j]
            rikai=[rikai[k]+A[j][k] for k in range(m)]
    if all([k>=x for k in rikai]):
        cost=min(cost, tmp)
        
if cost!=10**10:
    print(cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = [int(i) for i in input().split()]
C = []
B = []
for i in range(N):
    c, *a = [int(i) for i in input().split()]
    C.append(c)
    B.append(a)
minv = 10**18
for bit in range(1<<N):
    c = 0
    u = [0]*M
    for i in range(N):
        if(1 & bit >> i):
            c += C[i]
            for j in range(M):
                u[j] += B[i][j]

    if all([u[i] >= X for i in range(M)]):
        minv = min(minv, c)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
costs = []
skills = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    cost = tmp[0]
    skill = tmp[1:]
    costs.append(cost)
    skills.append(skill)


min_cost = float("inf")
for i in range(1 << n):
    cur_skill = [0] * m
    cur_cost = 0
    for j in range(n):
        if (i >> j & 1) == 1:
            cur_cost += costs[j]
            for k in range(m):
                cur_skill[k] += skills[j][k]
    flag = True
    for j in range(m):
        if cur_skill[j] < x:
            flag = False
    if flag:
        min_cost = min(min_cost, cur_cost)

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

Submission status: Accepted

Solution code:
N, M, X = list(map(int, input().split()))
costs = []
As = []
for i in range(N):
    t = list(map(int, input().split()))
    costs.append(t[0])
    As.append(t[1:])
ans = -1
for i in range(2 ** N):
    tot = [0] * M
    cost = 0
    for j in range(N):
        if i >> j & 1:
            cost += costs[j]
            for k in range(M):
                tot[k] += As[j][k]
        flag = True
        for k in range(M):
            if tot[k] < X:
                flag = False
        if flag:
            if ans < 0:
                ans = cost
            else:
                ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
n,m,x=map(int,input().split())
c=[]
a=[]
for _ in range(n):
	s,*t=map(int,input().split())
	c.append(s)
	a.append(t)
ans=float("inf")
for i in range(2**n):
	l=[[0]*m]
	need=0
	for j in range(n):
		if i&(1<<j):
			l.append(a[j])
			need+=c[j]
	if all(sum(t)>=x for t in zip(*l)):
		ans=min(ans,need)
print(ans if ans!=float("inf") else -1)

Submission status: Accepted

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

cand = []
for i in range(2 ** n):
    text = []
    for j in range(n):
        if ((i >> j) & 1):
            text.append(j)
    cand.append(text)

ret = 10 ** 100

for item in cand:
    kakaku = 0
    rikai = [0] * m
    for val in item:
        kakaku += mtx[val][0]
        for j in range(1, m+1):
            rikai[j-1] += mtx[val][j]
    is_ok = True
    for val in rikai:
        if val < x:
            is_ok = False
            break
    if is_ok:
        ret = min(ret, kakaku)

if ret == 10 ** 100:
    print(-1)
else:
    print(ret)

Submission status: Accepted

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

ans=10**10
for n in range(2**N):
  bit=format(n,'0'+str(N)+'b')
  bit=list(map(int,bit))
  nedan=0
  tmp=[0]*M
  for a,c,b in zip(A,C,bit):
    if b==0:continue
    nedan+=c
    for i in range(M):
      tmp[i]+=a[i]
  if min(tmp)>=X and nedan<ans:
    ans=nedan
if ans==10**10:
  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)]

for i in range(N):
    t = [int(x) for x in input().split()]
    C[i] = t[0]
    A[i] = t[1:]

ans = float("inf")
for bit in range(2**N):
    score = [0] * M
    cost = 0
    for i in range(N):
        if (bit >> i) & 1:
            cost += C[i]
            for j in range(M):
                score[j] += A[i][j]

    is_ok = True
    for i in range(M):
        if score[i] < X:
            is_ok = False

    if is_ok:
        ans = min(ans, cost)

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):
    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]
        a = A[j]
        for k in range(M):
            t[k] += a[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:
inf = 10**15
mod = 10**9+7

n,m,x = map(int, input().split())
san = [list(map(int, input().split())) for i in range(n)]
ans = inf
for i in range(2**n):
    cost = 0
    judge = [0 for i in range(m)]
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 1だったら(オンだったら)
            for k in range(m):
                judge[k] += san[j][k+1]
            cost+=san[j][0]
    flag = True
    for l in range(m):
        if judge[l] < x:
            flag = False
            break
    if flag:
        ans = min(ans,cost)
if ans == inf:
    print(-1)
else:
    print(ans)