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 sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, m, x = na()
ca = nan(n)

ans = inf
for i in range(2 ** n):
    und = [0] * m
    money = 0
    for j in range(n):
        if (i >> j) & 1:
            c = ca[j][0]
            money += c
            for k in range(m):
                und[k] += ca[j][k + 1]
    flag = True
    for j in range(m):
        if und[j] < x:
            flag = False
    if flag:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import itertools
import math
n,m,x = ma()
cost = [0]*n
A = []
for i in range(n):
    co = list(ma())
    cost[i] = co[0]
    A.append(co[1:])
ans = 10**9
for i in range(2**n):
    tmp = 0
    cnt = [0]*m
    f = True
    for j in range(n):
        if i>>j &1:##book j buy
            tmp+=cost[j]
            for k in range(m):
                cnt[k] +=A[j][k]
    for c in cnt:
        if c<x:
            f =False
    if f:ans = min(ans,tmp)
if ans==10**9:
    print(-1)
else:print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

loop_number = pow(2, n)

minimum_first = pow(10, 10)

minimum = 0
minimum += minimum_first

data = np.zeros((n, m+1))

for i in range(n):
    data[i] = np.asarray(input().split(), dtype=np.uint32)

for i in range(loop_number):
    a_sum = np.zeros(m)
    c_sum = 0
    for j in range(n):
        if np.bitwise_and(i, pow(2,j)):
            a_sum += data[j][1:]
            c_sum += data[j][0]

    if np.min(a_sum) >= x and c_sum < minimum:
        minimum = c_sum

if minimum == minimum_first:
    print(-1)
else:
    print(int(minimum))

Submission status: Accepted

Solution code:
import numpy as np

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

books = []

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

books = np.array(books)

ok = 0
min_c = 100000000

for i in range(1 << n):
    ans = np.array([0 for j in range(m+1)])
    for k in range(n):
        if (i >> k & 1) == 1:
            ans += books[k]
    if ((ans[1:] - x) >= 0).all():
        ok = 1
        min_c = min(min_c, ans[0])

if not ok:
    print(-1)
else:
    print(min_c)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17

def check(books, x, i, m, n):
    ab = [0 for i in range(m)]
    ret = 0
    for k in range(n):
        if i % 2 == 1:
            book = books[k]
            for tab, b in enumerate(book[1:]):
                ab[tab] += b
            ret += book[0]
        i //= 2
    # print(bin(i), ab)
    for cab in ab:
        if cab < x:
            return INF

    return ret

def main():
    n, m, x = getList()
    books = [getList() for _ in range(n)]
    ans = INF
    for i in range(2**n):
        # print(i)
        tmp = check(books, x, i, m, n)
        if ans > tmp:
            ans = tmp

    if ans == INF:
        print(-1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0]*N
A = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
    for j, x in enumerate(map(int, input().split())):
        if j == 0:
            C[i] = x
        else:
            A[i][j-1] = x

ans = 10**5*12+1
for bit_pattern in range(2<<N-1):
    i = 0
    tmp = [0]*M
    cost = 0

    while bit_pattern > 0:
        if bit_pattern & 1:
            for j in range(M):
                tmp[j] += A[i][j]
            cost += C[i]
        bit_pattern >>= 1
        i += 1

    for j in range(M):
        if tmp[j] < X:
            break
        if j == M-1:
            ans = min(ans, cost)
if ans == 10**5*12+1:
    ans = -1
print(ans)

Submission status: Accepted

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

import itertools
PRD=list(itertools.product([0,1], repeat=N))

ans=10**15
for i in range(len(PRD)):
    scores=[0 for i in range(M)]
    money=0
    #print(PRD[i])
    for j in range(N):
        for k in range(M):
            scores[k]+=PRD[i][j]*A[j][k]
        money+=PRD[i][j]*C[j]
    #print(scores,money)
    if min(scores)>=X:
        ans=min(ans,money)

if ans==10**15:
    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],*aa = map(int,input().split())
    a[i]=aa

ans=10**50
for i in range(2**n):
    bi = bin(i)[2:].zfill(n)
    skill = [sum(a[k][j] for k in range(n) if bi[k]=="1") for j in range(m)]
    if all(s>=x for s in skill):
        cand = sum( c[i] for i in range(n) if bi[i]=="1")
        if cand<ans:
            ans=cand
if ans==10**50:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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


INF = 1 << 31
ans = INF
for i in range(1 << N):
    curr_cost = 0
    understanding = [0] * M
    for j in range(N):
        if i >> j & 1:
            curr_cost += costs[j]
            for k in range(M):
                understanding[k] += A[j][k]
    if min(understanding) >= X:
        ans = min(ans, curr_cost)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

min_price = None
for t in range(2 ** N):
    price = 0
    values = [0] * M
    for i in range(N):
        if (1 << i) & t:
            price += C[i]
            for j in range(M):
                values[j] += A[i][j]
    if all(X <= v for v in values) and (min_price is None or price < min_price):
        min_price = price
print(min_price if min_price is not None else -1)

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

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

def dfs(pos):
    global n,m,x,a,ca,ans
    if pos==n:
        res = 0
        comp = [0] * m
        for i in range(n):
            if a[i]:
                res += ca[i][0]
                for j in range(1,m+1):
                    comp[j-1] += ca[i][j]
        for i in range(m):
            if comp[i]<x:
                return
        ans = min(ans,res)
        return
    a[pos] = 0
    dfs(pos+1)
    a[pos] = 1
    dfs(pos+1)

def main():
    global n,m,x,a,ca,ans
    n,m,x = readInt()
    ca = []
    for i in range(n):
        ca.append(readInt())
    ans = INF
    a = [0] * n
    dfs(0)
    if ans==INF:
        print(-1)
    else:
        print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

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

L = [0]*n
C = [0]*n
for i in range(n):
    temp = list(map(int, input().split()))
    L[i] = temp[1:]
    C[i] = temp[0]

import itertools
ans = 10**18
for i in range(1, n+1):
    for p in itertools.combinations(range(n),i):
        #print(p)
        temp = [0]*m
        cost = 0
        for j in range(len(p)):
            A = L[p[j]]
            cost += C[p[j]]
            for k in range(m):
                temp[k] += A[k]
        flag = True
        for l in range(m):
            if temp[l] < x:
                flag = False
        if flag:
            ans = min(ans, cost)
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# もしかして：こるとんさん作

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

price = []
a = []

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

ans = 10 ** 10
for num in range(2 ** n):
    rikaido = [0] * m
    cost = 0
    for i in range(n):
        # i冊目を買うか
        buy = num & (1 << i) > 0
        if buy:
            for j in range(m):
                rikaido[j] += a[i][j]
            cost += price[i]
    
    target = True
    # 条件を満たすか
    for j in range(m):
        if rikaido[j] < x:
            target = False
    
    if target:
        ans = min(cost, ans)

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

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M, X = map(int, readline().split())
psum = 0
books = []
for i in range(N):
    c, *a = map(int, readline().split())
    assert len(a) == M
    books.append((c, a))
    psum += c


def solve():
    U = 1 << N
    minp = psum + 1
    for i in range(U):
        sel = i
        unds = [0] * M
        k = 0
        price = 0
        while (1 << k) < U:
            if (sel >> k) & 1:
                c, a = books[k]
                price += c
                for j in range(M):
                    unds[j] += a[j]
            k += 1
        if minp > price and all(x >= X for x in unds):
            minp = price

    if minp == psum + 1:
        return -1
    return minp


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
flag = False
price = 10 ** 7
for i in range(2 ** n):
    num = bin(2 ** n + i)
    flag2 = True
    temp_price = 0
    a = [0] * m
    for j in range(n):
        if num[-j-1] == "1":
            temp = data[j][1:]
            temp2 = data[j][0]
            temp_price += temp2
            for k in range(m):
                a[k] += temp[k]
    for j in range(m):
        if a[j] < x:
            flag2 = False
            break
    if flag2 == True:
        flag = True
        price = min(price, temp_price)
if flag == True:
    print(price)
else:
    print(-1)

Submission status: Accepted

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

ans=10**7
for i in range(2**n):
    cost=0
    res=[0]*m
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m):
                res[k]+=c[j][k+1]
            cost+=c[j][0]
    for j in range(m):
        if res[j]<x:
            break
        if res[j]>=x and j==m-1:
            if cost<ans:
                ans=cost
if ans==10**7:
    print('-1')
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,m,x = map(int, input().split()) 
# b = list(map(int, input().split()))
# n = int(input())
# a = [int(input()) for _ in range(n)]
ca =[]
for i in range(n):
    ca.append(list(map(int, input().split())))


ans = 10**9
for i in range(1 << n):
    abil = [0]*m
    val = 0
    for j in range(n):
        if ((i >> j) & 1):
            val += ca[j][0]
            for k in range(m):
                abil[k] += ca[j][k+1]
    if min(abil) >=  x:
        if val < ans:
            ans = val
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

def main():
    N,M,X = map(int, readline().split())
    CA = [[int(i) for i in readline().split()] for _ in range(N)]
    
    ans = 10**15
    for i in range(2**N):
        m = [0] * M
        c = 0
        flag = True
        for j in range(N):
            if (i >> j) & 1:
                c += CA[j][0]
                for k in range(1,M+1):
                    m[k-1] += CA[j][k]
        for a in m:
            if a < X:
                flag = False
                break
        if flag:
            ans = min(ans, c)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, x = map(int,input().split())
books = []
for i in range(n):
    books.append(list(map(int,input().split())))
mi = 10**100
s = "0"+str(n)+"b"

for i in range(2**n):
    p = [0 for j in range(m)]
    money = 0
    k = str(format(i, s))
    for j in range(n):
        if k[j] == "1":
            money += books[j][0]
            for l in range(m):
                p[l] += books[j][l+1]
    if min(p) >= x and mi > money:
        mi = money

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

Submission status: Accepted

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

ans = -1
for i in range(2 ** n):
    bi = list(bin(i)[2:].zfill(n))
    cost = 0
    understand = [0] * m
    for j, buy in enumerate(bi):
        if buy == "1":
            cost += c[j]
            for k in range(m):
                understand[k] += a[j][k]
    f = True
    for j in range(m):
        if understand[j] < x:
            f = False

    if f:
        if ans == -1:
            ans = cost
        else:
            ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
def solve():
    N,M,X = map(int,input().split())
    C = []
    A = []
    for i in range(N):
        val = list(map(int,input().split()))
        C.append(val[0])
        A.append(val[1:])
    
    ans = float('inf')
    for i in range(1 << N):
        money = 0
        points = [0] * M
        for j in range(N):
            if (i >> j) & 1:
                money += C[j]
                for k in range(M):
                    points[k] += A[j][k]
        
        for j in range(M):
            if points[j] < X:
                break
        else:
            ans = min(ans,money)

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


                
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

N, M, X = map(int, sys.stdin.readline().split())

books = []
for _ in range(N):
    tmp = list(map(int, sys.stdin.readline().split()))
    books.append(tmp)

ans = float("inf")
for i in range(1 << N):
    cost = 0
    scores = [0] * M
    for j in range(N):
        if i & (1 << j):
            cost += books[j][0]
            for k, score in enumerate(books[j][1:]):
                scores[k] += score
    for score in scores:
        if score < X:
            break
    else:
        ans = min(ans, cost)
            
print(-1 if ans == float("inf") else ans)

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


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


def llmi(n):
    return [lmi() for _ in range(n)]


def main():
    N, M, X = lmi()
    CA = llmi(N)

    def get_cost(set_of_bought):
        ans = 0
        for s in set_of_bought:
            ans += CA[s][0]
        return ans

    def check(set_of_bought):
        XX = [0] * M
        for s in set_of_bought:
            for i in range(M):
                XX[i] += CA[s][i + 1]
        if all(v >= X for v in XX):
            return True
        return False
    ans = INF
    for i in range(1 << N):
        cur = set()
        for n in range(N):
            if i>>n & 1:
                cur.add(n)
        # print(cur)

        if check(cur):
            ans = min(ans,get_cost(cur))
    if ans == INF:
        print(-1)
    else:
        print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,x = LI()
A = [LI() for _ in range(n)]

ans = inf
for i in range(1<<n):
    tmp = [0]*m
    preans = 0
    for j in range(n):
        if i >> j & 1:
            preans += A[j][0]
            for k,l in enumerate(A[j][1:]):
                tmp[k-1] += l
    for j in tmp:
        if j < x:
            break
    else:
        ans = min(ans, preans)
if ans == 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 _ in range(n)]
ans=10**9
for i in range(1,2**n):
    a=[0]*m
    price=0
    for j in range(n):
        if i>>j&1:
            for k in range(m):
                a[k]+=ca[j][k+1]
            price+=ca[j][0]
    cnt=0
    for j in range(m):
        if a[j]>=x:
            cnt+=1
    if cnt==m:
        ans=min(ans,price)
if ans==10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]
ans = 10**10
for i in range(2**N):
    cost = 0
    rikai = [0 for i in range(M)]
    for j in range(N):
        if i>>j&1:
            cost += A[j][0]
            for k in range(M):
                rikai[k] += A[j][k+1]
    b = True
    for k in range(M):
        if rikai[k] >= X:
            continue
        b = False
    if b:
        ans = min(ans,cost)
print(-1 if ans == 10**10 else ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, M, X = map(int, input().split())
    books = [list(map(int, input().split())) for _ in range(N)]
    ans = float("inf")
    for i in range(2**N):
        cost = 0
        score = [0] * M
        for j in range(N):
            if ((i >> j) & 1):
                cost += books[j][0]
                for k in range(1, M+1):
                    score[k-1] += books[j][k]
        flag = True
        for j in range(M):
            if score[j] < X:
                flag = False
                break
        if flag:
            ans = min(ans, cost)
    if ans == float("inf"):
        print("-1")
    else:
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

mi = 10**10
for i in range(2**n):
    skill = [0]*m
    price = 0
    for j in range(n):
        if (i>>j)&1:
            price += a[j][0]
            for k in range(m):
                skill[k] += a[j][k+1]
    for k in skill:
        if k<x:
            break
    else:
        mi = min(mi, price)
print(mi if mi<10**10 else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
dat = []
for i in range(n):
    l = list(map(int, input().split()))
    dat.append(l)
#print(dat)
res = 999999999999999999999999999
for i in range(2**n):
    pat = "{:020b}".format(i)
    pat = pat[::-1]
    #print(pat)
    cost = 0
    kekka = [0] * m
    for j in range(n):
        if pat[j] == "1":
            cost += dat[j][0]
            item = dat[j][1:]
            for k in range(m):
                kekka[k] += item[k]
    can = True
    #print(kekka)
    #print(">cost", cost)
    for k in range(m):
        if kekka[k] < x:
            can= False
    if can:
        #print("ok", cost)
        res = min(res, cost)

if res == 999999999999999999999999999:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
#n札の参考書
#mのアルゴリズム
#x以上

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

result=10**9

for i in range(2**n):
    understand=[0]*m
    cost=0
    for j in range(n):
        if i>>j&1:
            temp=ca[j]
            cost+=temp[0]
            for index,item in enumerate(temp[1:]):
                understand[index]+=item
    flag=0
    for item in understand:
        if item<x:
            flag=1
    if flag==0:
        result=min(cost,result)
if result==10**9:
    print(-1)
else:
    print(result)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string,decimal
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def SS(): return map(str,sys.stdin.readline().rstrip().split())
def II(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N,M,X = II()
CA=[list(map(int,list(input().split()))) for i in range(N)]
C_min = -1

for i in range(2 ** N):
  C_tmp = 0
  A_tmp = [0]*M
  for j in range(N):
    if ((i >> j) & 1):
      C_tmp += CA[j][0]
      for k in range(M):
        A_tmp[k] += CA[j][k+1]
  if all([l >= X for l in A_tmp]):
    if C_min == -1:
      C_min = C_tmp
    else:
      C_min = min(C_tmp,C_min)
print(C_min)

Submission status: Accepted

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

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

#print(C, A)
ans="-1"
for b in range(2**N):
    L=[0]*M
    cost=0
    for i in range(N):
        if b>>i&1==0:
            cost+=C[i]
            l=A[i]
            for j,a in enumerate(l):
                L[j]+=a
    if min(L)>=X:
        if ans=="-1":
            ans=cost
        else:
            ans=min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,m,x=MI()
    caa=LLI(n)
    caa=np.array(caa,dtype="i8")
    ans=10**9
    for bit in range(1<<n):
        cost = 0
        aa = np.zeros(m, dtype="i8")
        for i in range(n):
            if bit>>i&1:
                cost+=caa[i][0]
                aa+=caa[i][1:]
        if np.sum(aa>=x)==m and cost<ans:ans=cost

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

main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Cost = []
A = []
for _ in range(N):
    temp = list(map(int, input().split()))
    Cost.append(temp[0])
    A.append(temp[1:])
mincos = float('inf')

flag = False
for i in range(1, 2**N):
    cost = 0
    Learn = [0] * M
    for j in range(N):
        if (i >> j) & 1 == 1:
            cost += Cost[j]
            for k in range(M):
                Learn[k] += A[j][k]
    fla = True
    for a in range(M):
        if Learn[a] < X:
            fla = False
            break
    if fla:
        flag = True
        mincos = min(mincos, cost)

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

Submission status: Accepted

Solution code:
import numpy as np

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

MIN = 10 ** 7
for i in range(2**N):
    cost = 0
    result = np.array([0] * M)
    for j in range(N):
        if ((i>>j)&1):
            cost += CA[j][0]
            result += CA[j][1:]

    if all(result >=X):
        MIN = min(cost,MIN)
if MIN == 10**7:
    print(-1)
else:
    print(MIN)

Submission status: Accepted

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

def int2bit(n, l):
	ret = [0 for i in range(l)]
	i = 0
	while n > 0:
		ret[i] = n % 2
		i += 1
		n = n // 2
	return ret

MAX = 10**7
ans = MAX
for i in range(1, 2**N):
	b = int2bit(i, N)
	rikai = [0 for j in range(M)]
	for p in range(N):
		if b[p] == 1:
			for j in range(M):
				rikai[j] += B[p][j+1]
	if len([r for r in rikai if r < X]) == 0:
		ans = min(ans, sum([B[p][0] for p in range(N) if b[p] == 1]))
if ans == MAX:
	print(-1)
else:
	print(ans)

Submission status: Accepted

Solution code:
from itertools import product
inpl = lambda: list(map(int,input().split()))
N, M, X = inpl()
A = []
C = []
for _ in range(N):
    H = inpl()
    C.append(H[0])
    A.append(H[1:])

ans = -1
for s in product(range(2), repeat=N):
    U = [ sum( A[n][m] for n in range(N) if s[n]) for m in range(M)]
    for m in range(M):
        if U[m] < X:
            break
    else:
        P = sum(C[n] for n in range(N) if s[n])
        if ans < 0 or P < ans:
            ans = P
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M, X = (int(i) for i in input().split())
    A = []
    C = []
    for _ in range(N):
        c, *a = (int(i) for i in input().split())
        A.append(a)
        C.append(c)
    ans = 10**9
    for bit in range(1 << N):
        cur_m = 0
        cur_ri = [0]*M  # 理解度
        for i in range(N):
            if bit & (1 << i):
                cur_m += C[i]
                for j, a in enumerate(A[i]):
                    cur_ri[j] += a
        if all(ri >= X for ri in cur_ri):
            ans = min(ans, cur_m)
    print(ans if ans != 10**9 else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x1= map(int, input().split())
# 値段,上がる理解度
c= [list(map(int, input().split())) for i in range(n)]

ans=pow(10,9)
for i in range(2**n):
    cnt=0
    x=[0]*m
    for j in range(n):
        if (i>>j)&1:
            cnt+=c[j][0]
            for k in range(1,m+1):
                x[k-1]+=c[j][k]
    if min(x)>=x1:
        ans=min(cnt,ans)

if ans==pow(10,9):
    print(-1)

else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
cost=[]
for i in range(n):
    p=list(map(int,input().split()))
    cost.append(p[0])
    a.append(p[1:])
ans=-1
for i in range(pow(2,n)):
    temp=0
    lev=[0 for i in range(m)]
    for j in range(n):
        if i&(pow(2,j)):
            temp += cost[j]
            for k in range(m):
                lev[k] += a[j][k]
    if min(lev)>=x:
        if ans==-1:
            ans=temp
        else:
            ans=min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Cs = []
Ass = []
for _ in range(N):
    c, *a = list(map(int, input().split()))
    Cs.append(c)
    Ass.append(a)

INF = float('inf')
ans = INF
for i in range(2 ** N):
    score = [0] * M
    d = 1
    cost = 0
    for j in range(N):
        if i & d:
            cost += Cs[j]
            for k, s in enumerate(Ass[j]):
                score[k] += s
        d <<= 1
    for s in score:
        if s < X:
            break
    else:
        ans = ans if ans < cost else cost

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n, m, x = MAP()
arr = [LIST() for _ in range(n)]
c = [arr[i][0] for i in range(n)]
a = [arr[i][1:] for i in range(n)]

ans = inf
for i in range(1, n + 1):
    cmb = list(combinations(range(n), i))
    for lst in cmb:
        tmp = [0 for _ in range(m)]
        cst = 0
        for idx in lst:
            cst += c[idx]
            for j in range(m):
                tmp[j] += a[idx][j]
        flag = True
        for j in range(m):
            if tmp[j] < x:
                flag = False
        if flag:
            ans = min(ans, cst)
if ans == inf:
    print(-1)
else:
    print(ans)