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
 
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)
 
def main():
    import numpy as np
    from itertools import product
 
    n, m, x = list(map(int, readline().split()))
    a, c = [], []
    for i in range(n):
        c_temp, *a_temp = list(map(int, readline().split()))
        c.append(c_temp)
        a.append(a_temp)
 
    a = np.array(a)
    ans = INF
 
    for bit in product(range(2), repeat=n):
        price_total = 0
        learn_total = np.array([0] * m)
        for i in range(n):
            if bit[i] == 1:
                price_total += c[i]
                learn_total += a[i]
        if np.all(learn_total >= x):
            ans = min(ans, price_total)
 
    if ans == INF:
        print(-1)
    else:
        print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

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

m = 1e9
for i in range(2 ** N):
	total = [0] * (M+1)
	for j in range(N):
		if((i >> j) & 1):
			total = python_list_add(total, A[j])
	if(all(elem >= X for elem in total[1:])):
		m = min(total[0],m)
if m == 1e9:
	m = -1
print(m)

Submission status: Accepted

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

ans = float("inf")

for i in range(1<<n):
    cost = 0
    points = [0] * m
    for j in range(n):
        if i>>j & 1:
            cost += L[j][0]
            for k in range(m):
                points[k] += L[j][k+1]

    if min(points) >= x:
        ans = min(ans, cost)

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

else:
    print(ans)

Submission status: Accepted

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

states = []
for i in range(n):
    ca = list(map(int, input().split()))
    state = {"cost" : ca[0], "value" :ca[1:]}
    states.append(state)

def check(uselist : list):
    understandings = [0]*m
    cost = 0
    for i, islist in enumerate(uselist):
        if islist == 1:
            for j in range(m):
                understandings[j] += states[i]["value"][j]
            cost += states[i]["cost"]

    for i in range(m):
        if understandings[i] < x:
            return 1000000000
    return cost

ans = 1000000000

for uselist in itertools.product(range(2), repeat=n):
    ans = min(ans, check(uselist))

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

Submission status: Accepted

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

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

ans = float('inf')
for i in range(2 ** n):
    sum = 0
    l = [0] * m

    for j in range(n):
        if i >> j & 1:
            sum += cl[j]
            for k in range(m):
                l[k] += al[j][k]

    flg = all([e >= x for e in l])

    if flg:
        ans = min(ans, sum)

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

Submission status: Accepted

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

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

ans = float('inf')
for i in range(2 ** n):
    sum = 0
    l = [0] * m
    flg = False

    for j in range(n):
        if i >> j & 1:
            sum += cl[j]
            for k in range(m):
                l[k] += al[j][k]

    for e in l:
        if e < x:
            flg = True
            break

    if not flg:
        ans = min(ans, sum)

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

Submission status: Accepted

Solution code:
from itertools import product

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

states = []

for i in range(n):
    tmp = list(map(int, input().split()))
    state = {
        'cost': tmp[0],
        'value': tmp[1:]
    }
    states.append(state)


def check(use_list : list):
    gain = [0 for _ in range(m)]
    cost = 0
    for i, is_use in enumerate(use_list):
        if is_use:
            for j in range(m):
                gain[j] += states[i]['value'][j]
            cost += states[i]['cost']

    for j in range(m):
        if gain[j] < x:
            return 1000000000
    return cost

ans = 1000000000

for use_list in product(range(2), repeat=n):
    ans = min(ans, check(use_list))
if ans == 1000000000:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product
n, m, x = map(int, input().split())
c = []
a = []
for o in range(n):
    _ = list(map(int, input().split()))
    c.append(_[0])
    a.append(_[1:])
ans = 10**100
for p in product([0, 1], repeat=n):
    skill = [0] * m
    cost = 0
    for i in range(n):
        if p[i]:
            for j in range(m):
                skill[j] += a[i][j]
            cost += c[i]
    if min(skill) >= x:
        ans = min(ans, cost)
if ans == 10**100:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# 組み合わせの全探索

import itertools

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

prices = []
abilities = []

# 値段と1冊で向上させらる能力のリストを格納
for i in range(n):
    s = list(map(int, input().split()))
    abilities.append(s)

combinations = []

# 全組み合わせの計算
for i in range(1, len(abilities)+1):
    s = list(itertools.combinations(abilities, i))
    combinations.append(s)

# print(combinations)

# それぞれの組み合わせを取り出して、条件を満たすかどうか判定
# combinatinons C 1 ~ m までの組み合わせをバラして出す
for combs in combinations:
    # それぞれの組み合わせにバラす
    for i in range(len(combs)):
        counts = [0] * m
        price = 0

        comb = combs[i]
        # print(comb)
        
        # 組みわせの中から1個ずつ取り出す
        for j in range(len(comb)):
            # 値段を取り出して、計算
            a = comb[j]
            price += a[0]

            # 能力値だけのリスト
            b = a[1:]

            # 組み合わせ内の能力を全て足していく
            for k in range(m):
                counts[k] += b[k]
            
            # 参考書の能力が全てxを超えていれば、m個のokをもつリストを作成
            # 条件を満たす組み合わせ
            ans = ['ok' for num in counts if num >= x]
            if len(ans) == m:
                # その時の値段を記録
                prices.append(price)

# 最後に確認して、出力
if len(prices) >= 1:
    print(min(prices))
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X=[int(i) for i in input().split()]
C=[0]*N
A=[[] for i in range(N)]
for n in range(N):
    tmp=[int(i) for i in input().split()]
    C[n]=tmp[0]
    A[n]=tmp[1:]
Cmin=100000000000
minW=Cmin
for i in range(2**N):
    W=0
    T=[0]*M
    I=i
    cnt=0
    while I>0:
        if I%2==1:
            W+=C[cnt]
            T=[T[j]+A[cnt][j] for j in range(M)]
        cnt+=1
        I//=2
    if X<=min(T) and minW>W:
        minW=W
print(minW if minW!=Cmin else -1)

Submission status: Accepted

Solution code:
from itertools import combinations as Comb
N, M, X = map(int, input().split())
AC = [""] * N

for c in range(N):
    AC[c] = list(map(int, input().split()))

ans = 12 * 1000000
C = 0

def han(i): # 与えられた組み合わせがいいかどうか判定 i = ([C, A, ...], [C, A, ...], ...)
    global going, C
    A_wa = [0] * M
    for c in i:
        for co in range(1, M + 1, 1):
            A_wa[co - 1] += c[co]
        C += c[0]
    if min(A_wa) >= X:
        going = True
        

for c in range(1, N + 1, 1):
    lll = list(Comb(AC, c))
    for z in lll:
        going = False
        C = 0
        han(z)
        if going and C < ans:
            ans = C
if ans != 12 * 1000000:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X = map(int, input().split())
C = [0]*(N+1) #C[0]は使わない
A = [[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):
    C[i], *A[i][1:] = map(int, input().split())

MAX = 10**5 * N + 1
minprice = MAX
for b in range(2**N):
    price = 0
    abilitylist = [0]*(M+1)
    for i in range(1,N+1):
        if b >> (i-1) & 1 == 1:
            price += C[i]
            abilitylist = [x + y for x,y in zip(abilitylist, A[i])]
    
    flag = True
    for ability in abilitylist[1:]:
        if ability < X:
            flag = False
            break
    
    if flag:
        minprice = min(minprice, price)

ans = minprice if minprice != MAX else -1
print(ans)

Submission status: Accepted

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

min_money = 1e10
for i in range(2**N):
    buy_list = [0] * N
    skill = [0] * M
    money = 0
    
    for j in range(N):
        if i % 2 == 0:
            buy_list[j] = 1
        i //= 2
    for buy_idx, ca in enumerate(c_a_list):
        if buy_list[buy_idx] == 1:
            for a_idx, a in enumerate(ca[1:]):
                skill[a_idx] += a
            money += ca[0]
    for s_idx, s in enumerate(skill):
        if s < X:
            break
        if s_idx == M-1:
            min_money = min(min_money, money)
if min_money == 1e10:
    print(-1)
else:
    print(min_money)

Submission status: Accepted

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

ans = 10**10
for i in range(1<<n):
    li = []
    
    cost = 0
    for j in range(n):
        if (i>>j)&1:
            li.append(score[j])
            cost +=pr[j]

    score_all = [0 for l in range(m)]
    for k in range(len(li)):
        for j in range(m):
            score_all[j] +=li[k][j]
    if all([y>=x for y in score_all]):
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    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:
import itertools

n, m, x = map(int, input().split())
a = []
c = []
for i in range(n):
    line = list(map(int, input().split()))
    c.append(line[0])
    line.pop(0)
    a.append(line)
p = list(map(list, list(itertools.product([0,1], repeat=n))))
flag = 1
min_money = 10**10
for pattern in p:
    flag_1 = 0
    alg = [0 for i in range(m)]
    money = 0
    for i in range(n):
        if pattern[i]:
            money += c[i]
            for j in range(m):
                alg[j] += a[i][j]
    for i in range(m):
        if alg[i] < x:
            flag_1 = 1
    if flag_1:
        continue
    min_money = min(money, min_money)
    flag = 0
if flag:
    print(-1)
else:
    print(min_money)

Submission status: Accepted

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

    skill = [0]*M
    get_skill = [0]*M
    money = 0

    ans = 99999999
    back = []

    for i in range(2**N):
        #bit全探索
        for j in range(N):
            if ( (i>>j)&1 ):
                back.append(book[j])
        #print(back)

        for A in back:
            #print(A)
            money += A[0]
            for j in range(1,M+1):
                skill[j-1] += A[j]

        #print(skill)

        for k in range(M):
            if skill[k] >= X:
                get_skill[k] += 1

        if 0 not in get_skill:
            if money < ans:
                ans = money

        skill = [0]*M
        get_skill = [0]*M
        money = 0
        back = []

    if ans == 99999999:
        ans = -1
        return ans
    else:
        return ans

print(main())

Submission status: Accepted

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


def toBook(line):
    xs = line.split()
    cost = int(xs[0])
    values = list(map(int, xs[1:]))
    return (cost, values)


Books = [toBook(input()) for i in range(N)]
maxCost = 10 ** 15


def isSatisfied(xs):
    return all([x >= X for x in xs])


def rec(i, proficiency, totalCost):
    if i == N:
        if isSatisfied(proficiency):
            return totalCost
        else:
            return maxCost
    else:
        _proficiency = list(map(add, proficiency, Books[i][1]))
        _totalCost = totalCost + Books[i][0]
        cost1 = rec(i + 1, proficiency, totalCost)
        cost2 = rec(i + 1, _proficiency, _totalCost)
        return min(cost1, cost2)


cost = rec(0, [0] * M, 0)
if cost == maxCost:
    print("-1")
else:
    print(cost)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Xlist = []
ans = -1
for i in range(N):
    Nlist = list(map(int, input().split()))
    for j in range(len(Xlist)):
        sumList = [x + y for (x, y) in zip(Nlist, Xlist[j])]
        Xlist.append(sumList)
        if min(sumList[1:]) >= X:
            if ans == -1:
                ans = sumList[0]
            elif ans > sumList[0]:
                ans = sumList[0]
    Xlist.append(Nlist)
    if min(Nlist[1:]) >= X:
        if ans == -1:
            ans = Nlist[0]
        elif ans > Nlist[0]:
            ans = Nlist[0]

print(ans)

Submission status: Accepted

Solution code:
import itertools
from operator import add
n,m,x = map(int,input().split())
li = []
money=100000000
for i in range(n):
	li.append(list(map(int,input().split())))

for i in range(1, n+1, 1):
	for v in itertools.combinations(li, i):
		sum_li = [0]*(m+1)
		for j in v:
			sum_li = [x+y for (x, y) in zip(sum_li,j)]
		for j in range(m):
			if(sum_li[j+1] < x):
				break
		else:
			money = min(sum_li[0], money)

print(money if(money != 100000000) else -1)

Submission status: Accepted

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

val0 = [0]*(M+1)
ans = 10**9
val = []
for _ in range(N):
    val.append(list(map(int, input().split())))

for i in range(2**N):
    ls = ["+"]*N
    for j in range(len(ls)):
        if (i >> j) & 1:
            ls[j] = "-"
    for m, n in enumerate(ls):
        if n == '+':
            val0 = [x + y for (x, y) in zip(val0, val[m])]
    if ans > val0[0]:
        for k, l in enumerate(val0[1:]):
            if l < X:
                break
            elif k == len(val0[1:])-1:
                ans = val0[0]
    val0 = [0]*(M+1)
        
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ans = 10**10
for bit in range(1 << n):
    score_sum = [0 for _ in range(m)]
    price_sum = 0
    for i in range(n):
        if ((bit >> i) & 1) == 1:
            price_sum += price[i]
            for j in range(m):
                score_sum[j] += book[i][j]
    flag = True
    for v in score_sum:
        if v < x:
            flag = False
    if flag:
        ans = min(ans, price_sum)

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

Submission status: Accepted

Solution code:
from operator import add

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

book_list = []
check = {}

for i in range(N):
    book_list.append(input().split(' '))


def search_min_cost(cost, skill, i):

    # スキルが超えていたらそれ以上は投資する必要がない
    if all([x >= X for x in skill]):
        return cost

    # もう本がない場合
    if len(book_list) == i:
        return -1

    book = book_list[i]

    book_cost = int(book[0])
    book_skill = list(map(int, book[1:]))

    # 本を使った後のスキル結果
    use_skill = list(map(add, skill, book_skill))
    use_cost = search_min_cost(cost + book_cost, use_skill, i + 1)

    # この本は使わなかった場合
    no_use_cost = search_min_cost(cost, skill, i+1)

    if use_cost == -1:
        return no_use_cost

    if no_use_cost == -1:
        return use_cost

    if use_cost > no_use_cost:
        return no_use_cost

    return use_cost


cost = search_min_cost(0, [0] * M, 0)
print(cost)

Submission status: Accepted

Solution code:
a,b,c=map(int,input().split())
d=[]
for i in range(a):
    n=list(map(int,input().split()))
    d.append(n)
ans=[]
q=len(d)
for i in range(2**q):
    score=[0]*b
    total=0
    n=0
    for j in range(q):
        if ((i>>j)&1):
            for m in range(b):
                score[m]+=d[j][m+1]
            total+=d[j][0]
    for mm in range(b):
        if score[mm]>=c:
            n+=1
    if n==b:
        ans.append(total)

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

Submission status: Accepted

Solution code:
def check(idxs_):
    rikaido = [0 for i in range(m)]
    cost_ = 0
    for i in idxs_:
        for j in range(m):
            rikaido[j] += a[i][j]
        cost_ += c[i]
    for i in range(m):
        if rikaido[i] < x:
            cost_ = 9999999
    return cost_


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

mini = 9999999

for i in range(2 ** n):
    _ = []
    for j in range(n):
        if ((i >> j) & 1):
            _.append(j)
    cost = check(_)
    if cost < mini:
        mini = cost
    # print(mini)

if mini == 9999999:
    mini = -1

print(mini)

Submission status: Accepted

Solution code:
def main():
    n,m,x = map(int,input().split())
    a = [[] for _ in range(n)]
    c = [0] * n

    INF = 10 ** 9
    ans = INF

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

    for s in range(0,1<<n):
        smart = [0] * m
        cost = 0
        for i in range(n):
            if(s>>i) % 2 == 0:continue
            cost += c[i]
            for j in range(m):
                smart[j] += a[i][j]
        ok = True
        for i in range(m):
            if smart[i] < x:
                ok = False
        if ok:
            ans = min(ans,cost)
    if ans == INF:
        ans = -1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = -1

for i in range(1<<n):
    csum = 0
    mlst = [0]*m
    for j in range(n):
        if (i>>j)&1==1:
            csum += c[j]
            for k in range(m):
                mlst[k]+=a[j][k]
    if all(X >= x for X in mlst):
        if ans == -1:
            ans = csum
        else:
            ans = min(ans,csum)

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):
    B = list(map(int, input().split()))
    C[i] = B[0]
    A[i] = B[1:]

ans = 1e20
for i in range(2**N):
    cost = 0
    vals = [0] * M
    for j in range(N):
        if (i >> j & 1) == 1:
            cost += C[j]
            vals = [vals[k] + A[j][k] for k in range(M)]
    if min(vals) >= X and cost <= ans:
        ans = cost 

if ans == 1e20:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

ANS = 10**9

for i in it:
    arr = [0]*(M+1)
    for j in range(N):
        arr = list(map(lambda x,y: x+y*i[j], arr, l[j]))
    if all([k>=X for k in arr[1:]]):
        ANS = min(ANS,arr[0])
if ANS == 10**9:
    ANS = -1
print(ANS)

Submission status: Accepted

Solution code:
import itertools
n,m,x =map(int,input().split())
lists=[]
understand=[0]*m
num= [0,1]
ans = 10**10000
patterns = list(itertools.product(num, repeat=n))
for i in range(n):
    lists.append(list(map(int,input().split())))
total =0
#本を買う組み合わせ
for i in patterns:
    pattern = list(i)
    total =0
    understand=[0]*m
    for l in range(n):
        if pattern[l] ==1:
            total += lists[l][0]
            for k in range(m):
                understand[k] += lists[l][k+1]
    understand.sort()
    if understand[0] >= x:
        ans = min(ans,total)
if ans == 10**10000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
lst = [[int(x) for x in input().split()] for _ in range(N)]
ret = 100 ** 100
for mask in range(2 ** N):
    C = [0] * M
    cst = 0
    for i in range(N):
        if (mask >> i) & 1:
            cst += lst[i][0]
            for j in range(1, M + 1):
                C[j - 1] += lst[i][j]
    if min(C) >= X:
        ret = min(ret, cst)
if ret < 100 ** 100:
    print(ret)
else:
    print(-1)

Submission status: Accepted

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

ans = float("inf")
for bit in range(1 << n):
    rikai = [0 for i in range(m)]
    count = 0

    for i in range(n):
        if bit & (1 << i):
            for j in range(m):
                rikai[j] += a[i][j]
            count += c[i]

    flag = True
    for i in rikai:
        if i < x:
            flag = False
            break

    if flag:
        ans = min(ans, count)

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

Submission status: Accepted

Solution code:
from itertools import combinations as comb

n,m,x=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(n)]
smmin=None
for j in range(1,n+1):
    for z in comb(range(1,n+1),j):
        und=[0 for i in range(m)]
        sm=0
        for l in range(j):
            sm+=lst[z[l]-1][0]
            for k in range(1,m+1):
                und[k-1]+=lst[z[l]-1][k]
        for y in und:
            if y<x: break
        else :
            if not smmin: smmin=sm
            elif smmin>sm: smmin=sm
if not smmin: print(-1)
else : print(smmin)

Submission status: Accepted

Solution code:
from numpy import sort

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

INF = 10 ** 9
ans = INF
import itertools
for i in range(1,N + 1):
  for comb in itertools.combinations(range(N),i):
    cost = 0
    skills = [0] * M
    for c in comb:
      cost += C[c]
      for j in range(M):
        skills[j] += A[c][j]
    if cost >= ans:
      continue
    for s in skills:
      if s < X:
        break
    else:
      ans = cost

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

Submission status: Accepted

Solution code:
from numpy import cumsum

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

INF = 10 ** 9
ans = INF
import itertools
for i in range(1,N + 1):
  for comb in itertools.combinations(range(N),i):
    cost = 0
    skills = [0] * M
    for c in comb:
      cost += C[c]
      for j in range(M):
        skills[j] += A[c][j]
    if cost >= ans:
      continue
    for s in skills:
      if s < X:
        break
    else:
      ans = cost

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

Submission status: Accepted

Solution code:
import collections

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

INF = 10 ** 9
ans = INF
import itertools
for i in range(1,N + 1):
  for comb in itertools.combinations(range(N),i):
    cost = 0
    skills = [0] * M
    for c in comb:
      cost += C[c]
      for j in range(M):
        skills[j] += A[c][j]
    if cost >= ans:
      continue
    for s in skills:
      if s < X:
        break
    else:
      ans = cost

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

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[a] >= x for a 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):
    p = [j for j in map(int, input().split())]
    c.append(p[0])
    a.append(p[1:])
# print(n, m, x)
# for i in range(n):
#     print(c[i], a[i])
ans = 10**10

for i in range(1 << n):
    money = 0
    understand = [0]*m

    for j in range(n):
        if (i >> j) & 1 == 0:
            continue
        money += c[j]
        for k in range(m):
            understand[k] += a[j][k]
    for l in range(m):
        if understand[l] < x:
            break
    else:
        ans = min(ans, money)


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

Submission status: Accepted

Solution code:
import itertools

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

prices = []

for r in range(n):
    for tup in (map(list,itertools.combinations(all_list, r+1))):
        sum = [0] * (m+1)
        for lis in tup:
            for i, val in enumerate(lis):
                sum[i] += val
        for i in range(m):
            if sum[i+1] < x:
                break
        else:
            prices.append(sum[0])

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

Submission status: Accepted

Solution code:
n, m, x = [*map(int, input().split())]
k = [[*map(int, input().split())] for _ in range(n)]
ans = 10 ** 9

for i in range(2 ** n):
    cost = 0
    skills = [0] * m
    for j in range(n):
        if ((i >> j) & 1):
            cost += k[j][0]
            for s, t in enumerate(k[j][1:]):
                skills[s] += t
            if all(map(lambda skill: skill >= x, skills)):
                ans = min(ans, cost)
print(-1 if ans == 10 ** 9 else ans)

Submission status: Accepted

Solution code:
import numpy as np

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

INF = 10 ** 9
ans = INF
import itertools
for i in range(1,N + 1):
  for comb in itertools.combinations(range(N),i):
    cost = 0
    skills = [0] * M
    for c in comb:
      cost += C[c]
      for j in range(M):
        skills[j] += A[c][j]
    if cost >= ans:
      continue
    for s in skills:
      if s < X:
        break
    else:
      ans = cost

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

Submission status: Accepted

Solution code:
def resolve():
	(N, M, X), *T = [[*map(int, i.split())] for i in open(0)]
	ans = []
	for i in range(1, 2**N):
		tmp = []
		for j in range(N):
			if i>>j & 1 == 1:
				tmp.append(T[j])
		c, *a = map(sum, zip(*tmp))
		if min(a) >= X:
			ans.append(c)
	if ans:
		print(min(ans))
	else:
		print(-1)
resolve()

Submission status: Accepted

Solution code:
import itertools

N,M,X= (int(x) for x in input().split(' '))
all_book =[]
min_price = 10**5*12 +1
c_lst = []
for i in range(N):
    book_lst= [int(x) for x in input().split(' ')]
    all_book.append(book_lst)
for k in range(1,N+1):
    for m in itertools.combinations(all_book, k):
        if len(m) > 1:
            combined1 = [i*0 for i in range(M+1)]
            for i in range(len(m)):
                combined1 = [x + y for (x, y) in zip(combined1, m[i])]
            c_lst.append(combined1)
        elif len(m) == 1:
            c_lst.append(m[0])
for l in range(len(c_lst)):
    if min(c_lst[l][1:M+1]) >= X:
        if min_price > c_lst[l][0]:
            min_price = c_lst[l][0]
if min_price == 10**5*12 +1:
    min_price = -1

print(min_price)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

all_df = np.zeros((1,M+1))
for n in range(N):
  A = [int(i) for i in input().split()]
  all_df = np.vstack([all_df, np.array(A).reshape(1,-1)])
all_df = all_df[1:]

cost = N * (10**6)
for pattern in itertools.product([0,1], repeat=N):
  result = all_df[np.array(pattern).astype(bool)].sum(axis=0)

  if (X > result[1:]).sum() > 0:
    pass
  else:
    if result[0] < cost:
      cost = result[0]

if cost == N * (10**6):
  print(-1)
else:
  print(int(cost))

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
price = []
for i in range(2 ** n):
    cnt = [0]*m
    price_temp = 0
    for j in range(n):
        if (i >> j) & 1:
            price_temp += c[j][0]
            for k in range(m):
                cnt[k] += c[j][k+1]
    if all(s >= x for s in cnt):
        price.append(price_temp)
print(min(price) if len(price) > 0 else -1)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for i in range(N)]
kotae=[]
def saiki(A):
    if len(A)==N:
        goukei=[0]*M
        onedan=0
        for i in range(N):
            if A[i]==1:
                for j in range(M):
                    goukei[j]+=CA[i][j+1]
                onedan+=CA[i][0]
        #print(goukei)
        if min(goukei)>=X:
            kotae.append(onedan)
        return
    for i in range(2):
        A.append(i)
        saiki(A)
        A.pop()
saiki([])
if len(kotae)==0:
    print(-1)
    exit()
print(min(kotae))