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

const = [[0],[1]]
while True:
    if len(const[0]) == N:
        break
    temp = []
    for a in const:
        temp.append(a + [0])
        temp.append(a + [1])
    const = temp

ans = float("inf")
for c in const:
    total = 0
    temp = [0 for _ in range(M)]
    for i, v in enumerate(c):
        if v == 1:
            total += A[i][0]
            for j, a in enumerate(A[i][1:]):
                temp[j] += a
    flag = True
    for t in temp:
        flag = flag and (X <= t)
    if flag:
        ans = min(ans, total)

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

ans = float('inf')
for i in range(1,2**N):
    bits = []
    bit = bin(i)[2:].zfill(N)
    check = [0] * M
    cost = 0
    for j in range(N):
        if bit[j] == '1':
            bits.append(j)
    for j in bits:
        check = python_list_add(check,book[j][1:])
        cost += book[j][0]
    if min(check) >= X and ans > cost:
        ans = cost
print(ans if ans != float('inf') else -1)

Submission status: Accepted

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

S = [list(map(int, input().split())) for i in range(n)]
 
ans = 10 ** 7
 
for i in range(2 ** n):

    total = 0
    cnt = [0] * m
 
    for j in range(n):
 
        if (i >> j) & 1:

            total += S[j][0]
            for l in range(m):
                cnt[l] += S[j][l+1]
 
        else:
            continue
    
    nums = [k for k in cnt if k >= x]
    if len(nums) == m:
        ans = min(ans, total)

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

else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a = [list(map(int,input().split())) for _ in range(n)]
import itertools
Cal2 = []
for i in range(1,n+1):
    C = list(itertools.combinations(a,i))
    Cal=[0]*len(C)
    for k in range(len(C)):
        ch=[0]*m
        for l in range(i):
            for j in range(1,m+1):
                ch[j-1]+=C[k][l][j]
            else:
                Cal[k] += C[k][l][0]
        else:
            if min(ch)>=x:
                Cal2.append(Cal[k])
if len(Cal2)==0:
    print(-1)
else:
    print(min(Cal2))

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ans=float('INF')
l=[]
for i in range(n):
    a=list(map(int,input().split()))
    l.append(a)
for i in range(2**n+1):
    L=[0]*(m+1)
    b=format(i,'b')
    b='0'*(n-len(b))+str(b)
    for j in range(n):
        if b[j]=='1':
            for k in range(m+1):
                L[k]+=l[j][k]
    if min(L[1:])>=x:
        ans=min(ans,L[0])
if ans!=float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

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

import itertools
ans = float("inf")
for i in itertools.product([0, 1], repeat=N):
    # print(i)
    point = [0] * M
    ans_p = 0
    for j, c in zip(i, C):

        if j == 1:
            ans_p += c[0]
            for p, a in enumerate(c[1:]):
                point[p] += a
    flag = 0
    # print(point)
    for p in point:
        if p < X:
            flag = 1
    if flag == 0:
        ans = min(ans_p, ans)
if ans == float("inf"):
    print(-1)
else:

    print(ans)

Submission status: Accepted

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

def main():
    N, M, X = map(int, input().split())
    C = [0] * N
    A = []
    for n in range(0, N):
        l = input().split()
        C[n] = int(l[0])
        A.append([int(i) for i in l[1:]])

    min_cost = sum(C) + 1
    globalCanAchive = False
    for i in range(1,N+1):
        for comb in itertools.combinations(range(N), i):
            canAchive = True
            for m in range(M):
                r = sum([A[n][m] for n in comb])
                if (r < X):
                    canAchive = False
                    break
            if (canAchive):
                globalCanAchive = True
                cost = sum([C[n] for n in comb])
                min_cost = min(min_cost, cost)

    if (globalCanAchive):
        print(min_cost)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 10**9

for i in range(1<<N):
    cost = 0
    tisiki = np.array([0]*M)
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            cond[j] = 1
    
    for k in range(N):
        if cond[k]==1:
            b = book[k]
            cost += b[0]
            tisiki += np.array(b[1:])
    
    if np.all(tisiki>=X):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

CA = np.array(CA)
CAsum = CA.sum(axis=0)
cmin = CAsum[0]

if np.any(CAsum[1:] < X):
    cmin = -1
else:
    for i in range(2**N):
        casum = np.zeros(M+1)
        for j in range(N):
            if((i >> j) & 1):
                casum += CA[j]
        if np.all(casum[1:] >= X):
            cmin = min(cmin,casum[0])

print(int(cmin))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np

# 標準入力の取得
N, M, X = list(map(int, input().split()))
C = []
A = []
for n in range(N):
    line = list(map(int, input().split()))
    C.append(line[0])
    A.append(line[1:])

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

# 求解処理
result = sum(C)
canAchieve = False
for i in range(2**N):
    cost = 0
    skill = np.zeros(M)
    for j in range(N):
        if ((i >> j) & 1):
            cost += C[j]
            skill += A[j]

    if min(skill) >= X:
        result = min(result, cost)
        canAchieve = True

if not canAchieve:
    result = -1

# 結果出力
print(result)

Submission status: Accepted

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

books = []

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

ans = 1145141919

for i in range(2 ** N):
    abilities = [0] * M
    cost = 0
    for j in range(N):
        if ((i >> j) & 1):
            cost += books[j][0]
            for k in range(M):
                abilities[k] += books[j][k + 1]
        
        check = 0
        for x in range(M):
            if abilities[x] >= X:
               check += 1
        if check == M:        
            ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
def dfs(c, i, l):
    if i == n:
        for j in l:
            if j < x:
                return None
        ans.append(c)
        return None
    else:
        for j in range(1, m + 1):
            l[j - 1] += ca[i][j]
        dfs(c + ca[i][0], i + 1, l)
        for j in range(1, m + 1):
            l[j - 1] -= ca[i][j]
        dfs(c, i + 1, l)
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for i in range(n)]
ans = []
li = [0] * m
dfs(0, 0, li)
try:
    print(min(ans))
except:
    print(-1)

Submission status: Accepted

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

book = [[0]*(m+1)]*n
result = 10**5 * 13
bit = []

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

for i in range(2**n):
    op = [0]*n
    for j in range(n):
        if ((i >> j) & 1):
            op[n - 1 - j] = 1
    bit.append(op)
    
for i in range(2**n):
    a = bit[i]
    flag = True
    check = [0]*(m+1)
    for j in range(n):
        if a[j] == 1:
            for k in range(m+1):
                check[k] += book[j][k]
    for l in range(1, m+1):
        if check[l] < x:
            flag = False
    if flag == True:
        result = min(result, check[0])
        
if result == 10**5 * 13:
    print(-1)
else:
    print(result)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
ans = 10**9
for i in range(2**n):
    book_list = [0] * (m+1)
    for j in range(n):
        if i>>j&1:
            for q,p in enumerate(a[j]):
                if q == 0:continue
                book_list[q-1] += p
            book_list[-1] += a[j][0]
    f = 1
    for y in range(m):
        if book_list[y] < x:
            f = 0
            break
    if f == 1:
        ans = min(ans,book_list[-1])
if ans == 10**9:
    print(-1);exit()
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

n, m, x = map(int, input().split())
c_list, a_list = [], []
for i in range(n):
    inp_list = list(map(int, input().split()))
    c_list.append(inp_list)

ans_list = []

for i in range(1,n+1,1):
    for comb in itertools.combinations(c_list,i):
        comb = np.array(comb)
        if i == 1:
            sum = comb[:,1:][0]
        else:
            sum = np.sum(comb[:,1:], axis=0)
        if all([j >= x for j in sum]):
            ans_list.append(np.sum(comb[:,0]))
if len(ans_list) > 0:
    print(min(ans_list))
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[]
for i in range(n):
  l.append(list(map(int,input().split())))
s=[]
a=[0]*(m+1)
s.append(a)
for i in range(n):
  newl=[]
  for j in s:
    new=[j[k]+l[i][k] for k in range(m+1)]
    newl.append(new)
  s.extend(newl)
ans=float('inf')
for i in s:
  for j in range(m):
    if i[j+1]<x:break
  else:
    ans=min(ans,i[0])
if ans==float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

total = float('inf')
ok = False
for pr in product([0, 1], repeat=n):
    tf = []
    for i in range(m):
        cnt = 0
        for j in range(n):
            if pr[j] == 1:
                cnt += A[j][i]
        if cnt >= x:
            tf.append(True)

    if len(tf) == m:
        ok = True
        ttl = 0
        for i,p in enumerate(pr):
            if p == 1:
                ttl += C[i]
        total = min(total, ttl)

if ok:
    print(total)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy

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

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

bl=[]
for i in range(2**n):
    bli=list(map(int,format(i,"b").zfill(n)))
    bl.append(bli)


p=-1
for i in range(2**n):
    u=numpy.zeros(m,dtype=int)
    pi=0
    for j in range(n):
        if bl[i][j]==1:
            pi+=l[j][0]
            for k in range(m):
                u[k]+=l[j][k+1]
    if min(u)>=x:
        if p==-1:
            p=pi
        else:
            p=min(p,pi)

print(p)

Submission status: Accepted

Solution code:
def ad(A, B):
    n = len(A)
    tmp = [0] * n
    for i in range(n):
        tmp[i] += A[i] + B[i]
    return tuple(tmp)

def judge(A):
    flag = True
    for i in A[1:]:
        if i < X:
            flag = False
    return flag

def rec(A, i):
    global ans
    if i == N:
        if judge(A) and ans > A[0]:
            ans = A[0]
        return 0
    rec(ad(A,C[i]), i + 1)
    rec(A, i + 1)

N, M, X = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for _ in range(N)]
A = tuple([0]*(M+1))
ans = 12*(10**5) + 1
rec(A, 0)
if ans == 12*(10**5) + 1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ca = [[]]*n

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

min = 10**15

for i in range(2**n):
    bin_i = bin(i)
    sum = 0
    point = [0]*m
    flag = 1
    l = len(bin_i)-2
    for j in range(l):
        if bin_i[-j-1] == "1":
            sum += ca[j][0]
            for k in range(m):
                point[k] += ca[j][k+1]

    for j in range(m):
        if point[j] >= x:
            pass
        else:
            flag = 0

    if flag:
        if sum <= min:
            min = sum

if min == 10**15:
    print("-1")
else:
    print(min)

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())))

CA = np.array(CA)
ans = []
for i in range(2 ** N):
  tmp = [False] * (N)
  pattern = []
  for j in range(N):
    if i >> j & 1:
      tmp[j] = True
  if len(CA[tmp]) == 0:
    continue
  pattern = CA[tmp]
  pattern = pattern.reshape(-1, M+1)
  if sum(pattern[:, 1:M+1].sum(axis=0) >= X) == M:
    price = pattern[:, 0].sum()
    ans.append(price)
if len(ans) == 0:
  print(-1)
  exit()
print(min(ans))

Submission status: Accepted

Solution code:
possibility = False

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

result = 10**8

for i in range(1, 2 ** N):
    cost = 0
    rikai = [0] * M
    for j in range(N):
        if (i >> j & 1):
            cost += C[j]
            for k in range(M):
                rikai[k] += A[j][k]
    if sum(map(lambda x: x >= X, rikai)) == M:
        possibility = True
        result = min(cost, result)

print(result if possibility else - 1)

Submission status: Accepted

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

ans_mem = [0]*(m+1)
ans = 10**10
for i in range(2**n):
    ans_mem = [0]*(m+1)
    a = '0'*(n-len(bin(i))+2)+bin(i)[2:]
    for j,k in enumerate(a):
        if int(k) == 1:
            for l in range(0,m+1):
                ans_mem[l]+=ca[j][l]
    if min(ans_mem[1:])>=x:
        ans = min(ans,ans_mem[0])

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

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
N,M,X = map(int, input().split())
matrix = np.array([list(map(int, input().split())) for _ in range(N)])

min_price = 1e9
for n in range(N):
  for texts in combinations(matrix, n+1):
    summation = np.sum(texts, axis=0)
    price = summation[0]
    if all(summation[1:] >= X):
      if price < min_price:
        min_price = price

print(min_price if min_price < 1e9 else -1)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math


N, M, X = [int(x) for x in stdin.readline().rstrip().split()]
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
ans = [0 for i in range(M+1)]
temp = [10000000000000000000 for i in range(M+1)]
B = [0 for i in range(M+1)]
for i in range(N):
    for k in range(1, M+1):
        B[k] += A[i][k]
for i in range(1, len(B)):
    if B[i] < X:
        print(-1)
        sys.exit()
for i in range(1, 2**N):
    ans = [0 for i in range(M+1)]
    bit = list(format(i, 'b'))
    if len(bit) < N:
        for i in range(N-len(bit)):
            bit.insert(0, '0')
    for i, v in enumerate(bit):
        if v == '1':
            for j in range(M+1):
                ans[j] += A[i][j]
    # print(ans)
    for p in range(1, M+1):
        if ans[p] < X:
            break
        if p == M:
            if ans[0] < temp[0]:
                for j in range(M+1):
                    temp[j] = ans[j]
print(temp[0])

Submission status: Accepted

Solution code:
import itertools

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

alg = [0]*m

l = range(n)

ans = 10**9
for i in range(1, n+1):
    for books in itertools.combinations(lst, i):
        alg = [0]*m
        money = 0
        for book in books:
            money += book[0]
            skills = book[1:]
            alg = [x+y for (x, y) in zip(alg, skills)]

        judge = True
        for i in alg:
            if i < x:
                judge = False

        if judge:
            if ans > money:
                ans = money

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

else:
    print(ans)

Submission status: Accepted

Solution code:
n , m , x = map(int,input().split())
c = []
a = []
for i in range(n):
    l = list(map(int,input().split()))
    c. append(l[0])
    a.append(l[1:m+1])
S = sum(c)
ans = S +1
for i in range(2**n):
    cost = 0
    sum = [0]*m
    for j in range(n):
        if ((i>>j)&1):
            cost += c[j]
            sum = [x + y for (x,y) in zip(sum,a[j])]  
            if all(i>=x for i in sum) == True:
                obj = sum
                ans = min(ans , cost)  
if ans > S:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

""" Input
S = input().rstrip()
N = int(input())
A = np.array(input().split(), dtype=np.float64)
D = [int(input()) for _ in range(N)]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
"""

N, M, X = map(int, input().split())
algorithm = [0] * M

prices = []
rikai = []
for _ in range(N):
    C, *A = list(map(int, input().split()))
    prices.append(C)
    rikai.append(A)

idx = range(N)

prices_min = 10 ** 12
flag = False

for i, _ in enumerate(idx, 1):
    for candidate in itertools.combinations(idx, r=i):

        total = 0
        for c in candidate:
            c_arr = np.array(rikai[c])
            total += c_arr

        if np.all(total >= X):
            flag = True
            price = 0
            for c in candidate:
                price += prices[c]

            prices_min = min(price, prices_min)


print(prices_min if flag else '-1')

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
b = [list(map(int, input().split())) for _ in range(n)]
ans = float("inf")
for s in itertools.product([True, False], repeat=n):
    c = 0
    t = [0]*m
    for i in range(n):
        if s[i]:
            c += b[i][0]
            for j in range(m):
                t[j] += b[i][j+1]
    for j in range(m):
        if t[j] < x:
            break
    else:
        ans = min(c, ans)
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

# 全探索

ans = n * 10 ** 5
flag = False
for bit in range(2 ** n):  # bit 1000101010
    money = 0
    levels = np.array([0] * m)
    for j in range(n):  # 0 <= j < n
        if bit >> j & 1:
            money += C[j]
            levels += A[j]
    # すべて x 以上なら
    if np.all(levels >= x):
        flag = True
        ans = min(ans, money)

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

Submission status: Accepted

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

costs = []
for i in range(2 ** n):
    flag = True
    cost = 0
    algos = [0] * m
    op = [False] * n
    for j in range(n):
        if ((i >> j) & 1):
            op[n - j - 1] = True
    #print(op)
    for j in range(n):
        if op[j]:
            for k, u in enumerate(ca[j][1:]):
                algos[k] += u
            cost += ca[j][0]
    for j in algos:
        if j < x:
            flag = False
    if flag:
        costs.append(cost)

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

Submission status: Accepted

Solution code:
def main():
  import itertools
  from sys import stdin
  N, M, X = map(int, input().split())
  s_list = [list(map(int, stdin.readline().split())) for _ in range(N)]
  nums = [0, 1]
  min_cos = 10 ** 10
  for balls in itertools.product(nums, repeat=N):
    cos = 0
    score = [0] * M
    v = list(balls)
    for i in range(N):
      if v[i] == 1:
        cos += s_list[i][0]
        score = [x + y for (x, y) in zip(score, s_list[i][1:])]
    if min(score) >= X and cos < min_cos:
      min_cos = cos
  if min_cos == 10 ** 10:
    print(-1)
  else:
    print(min_cos)
    
  
main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for _ in range(n)]
c=[0]*n
ans=10**7
for i in range(n):
  c[i]=ca[i][0]
for i in range(2**n):
  l=[0]*m
  prime=0
  for j in range(n):
    if ((i >> j) & 1):
      prime+=c[j]
      for k in range(m):
        l[k]+=ca[j][k+1]
  if all([j>=x for j in l]):
    ans=min(ans,prime)
print(-1 if ans==10**7 else ans)

Submission status: Accepted

Solution code:
import numpy as np

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

CA = []
for i in range(N):
    s = input()
    CA.append(np.fromstring(s, np.int64, sep=" "))

CA = np.asarray(CA)
C = CA[:, 0]
A = CA[:, 1:]

def loop(i, x, total):
    if i == N:
        if (x >= X).all():
            return total
        else:
            return np.inf

    return min(
        loop(i+1, x, total),
        loop(i+1, (x+A[i]).clip(0, X), total+C[i])
    )

ans = loop(0, np.zeros_like(A[0]), 0)
if ans == np.inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

limit = 2 ** N
ans = (10 ** 5) * 13
for p in range(limit):
    t = 1
    U = [0] * M
    cost = 0
    for i in range(N):
        if p & t > 0:
            cost += C[i]
            for j in range(M):
                U[j] += A[i][j]
        t <<= 1
    if all([su >= X for su in U]):
        ans = min(cost, ans)

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

Submission status: Accepted

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

def list_sum(a, b):
    n = len(a)
    c = [0] * n
    for i in range(n):
        c[i] = a[i] + b[i]
    return c

def skilled(ca_sum, x):
    m = len(ca_sum) - 1
    ret = True
    for i in range(1, m+1):
        ret = ret and ca_sum[i] >= x
    return ret

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

    for i in range(2 ** n):
        ca_sum = [0] * (m+1)
        for j in range(n):
            if (i >> j) & 1:
                ca_sum = list_sum(ca_sum, ca[j])
        if skilled(ca_sum, x):
            c_list.append(ca_sum[0])

    if c_list == []:
        print(-1)
    else:
        c_list.sort()
        print(c_list[0])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')

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

res = INF
for i in range(2 ** N):
    books = []
    for j in range(N):
        if i & (1 << j):
            books.append(C[j])
    total = 0
    level = [0] * M
    for book in books:
        total += book[0]
        for idx, l in enumerate(book[1:]):
            level[idx] += l
    flag = True
    for lev in level:
        if lev < X:
            flag = False
    if flag:
        res = min(res, total)

if res == INF:
    print('-1')
else:
    print(res)

Submission status: Accepted

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

flg = False
ans = 10**12
for i in range(2**N):
    A = []
    for j in range(N):
        if ((i>>j) & 1):
            A.append(P[j])
#     print('####', A)
    value = 0
    algo = [0]*M
    for a in A:
        value += a[0]
        for i in range(1, M+1):
            algo[i-1] += a[i]
#     print(value, algo)
    cnt=0
    for al in algo:
        if al>=X:
            cnt+=1
    if cnt==M:
#         print('!!!!!!!!!!!!!')
        flg=True
        ans = min(ans, value)
if flg:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = []
for i in range(N):
  karilist = list(map(int, input().split()))
  CA.append(karilist)
ans = 0
for i in range(M):
  rikai = 0
  for j in range(N):
    rikai += CA[j][i+1]
  if rikai < X:
    ans = -1
    break

if ans == 0:
  ans = N*(10**5)
  for j in range(2**N):
    dame = 0
    rikaiM = [0 for i in range(M)]
    cost = 0
    for k in range(N):
      if (j >> k) & 1 == 1:
        cost += CA[k][0]
        for h in range(M):
          rikaiM[h] += CA[k][h+1]
    # 理解度計算終了
    for h in rikaiM:
      if h < X:
        dame = 1
        break
    if dame == 0:
      ans = min(ans, cost)
print(ans)

Submission status: Accepted

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

A = [[0] * m for _ in range(n)]
C = [0] * n

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


# 全組み合わせをためす
from itertools import product
bit = [0, 1]
lst = product(bit, repeat=n)


INF = 1 << 40
m_min = INF
for v in lst:
	res = [0] * m
	money = 0
	for i in range(n):
		if v[i] == 1: # 1->use
			for x in range(m):
				res[x] += A[i][x]
			money += C[i]
	if all([e >= X for e in res]):
		m_min = min(m_min, money)

print(m_min) if m_min != INF else print(-1)

Submission status: Accepted

Solution code:
import itertools

N, M, X = map(int, input().split())
ca = []
for _ in range(N):
  ca.append(list(map(int, input().split())))
  
ns = [i for i in range(N)]
price = 1000000000000
for r in range(1,N+1):
  for v in itertools.combinations(ns, r):
    flag = True
    for j in range(M):
      s = sum([ca[i][j+1] for i in v])
      if s < X:
        flag = False
        continue
    if flag:
      p = sum([ca[i][0] for i in v])
      price = min(price, p)
      
if price == 1000000000000:
  print(-1)
else:
  print(price)

Submission status: Accepted

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

i=0
while i<N:
    C[i]=list(map(int,input().split()))
    i+=1

ans=10**9
for i in range(2 ** N):
    bag = [0]*M
    total=0
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            a=0    
            for k in C[j][1:]:
                bag[a]+=k
                a+=1
            total+=C[j][0]  # フラグが立っていたら bag に果物を詰める
    if all(b>=X for b in bag):
        ans=min(ans,total)
    
if ans==10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
N, M, X = map(int, input().split())
C_list = []
A_list_list = []
for i in range(N):
    A_list = list(map(int, input().split()))
    C_list.append(A_list[0])
    A_list_list.append(A_list[1:])

N_list = [i for i in range(N)]
ans = 10 ** 10
for i in range(1, N + 1):
    for comb in itertools.combinations(N_list, i):
        temp_ans = 0
        for j in comb:
            temp_ans += C_list[j]
        if temp_ans >= ans:
            continue
        
        X_list = [0 for _ in range(M)]
        for j in comb:
            temp_A_list = A_list_list[j]
            for k in range(M):
                X_list[k] += temp_A_list[k]
        if len([X_list[i] for i in range(len(X_list)) if X_list[i] < X]) == 0:
            ans = min(ans, temp_ans)

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

Submission status: Accepted

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

purchase_l = [0]*n
cost = float('inf')
flag = True

while flag:
    skill = [0]*m
    cost_tmp = 0
    for i in range(n):
        for j in range(m):
            skill[j] += purchase_l[i]*ca[i][j+1]
    for s in skill:
        if s < x:
            break
    else:
        for i in range(n):
            cost_tmp += purchase_l[i]*ca[i][0]
        cost = min(cost, cost_tmp)
    for k in range(1,n+1):
        purchase_l[-k] += 1
        if purchase_l[-k] == 2:
            purchase_l[-k] = 0
        else:
            break
    else:
        flag = False

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

Submission status: Accepted

Solution code:
import itertools

n,m,x=map(int,input().split())
kin=[]
rika=[]
ans=10000000
for i in range(n):
    tmp=list(map(int,input().split()))
    kin.append(tmp[0])
    rika.append(tmp[1:])
#print(kin,rika)
tmpp=[0]*m
for i in range(1,n+1):
    for j in itertools.combinations(range(1,n+1), i):
        tmpp = [0] * m
        #print(j)
        for k in j:
            for l in range(m):
                tmpp[l]+=rika[k-1][l]
        #print(tmpp)
        if min(tmpp)>=x:
            kincou=0
            for k in j:
                kincou+=kin[k-1]
            ans=min(ans,kincou)
if ans==10000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, m, x = [int(i) for i in input().split()]
arr = []

for _ in range(n):
    arr.append([int(i) for i in input().split()])

min_amount = float('+inf')
has_sol = False

def dfs(idx, amt, skills):
    global arr
    global min_amount
    global x
    global has_sol

    if idx == len(arr):
        ok = all(j >= x for j in skills)

        if ok:
            has_sol = True
            min_amount = min(min_amount, amt)
        return

    dfs(idx+1, amt, skills)
    dfs(idx+1, amt+arr[idx][0], [j+arr[idx][i+1] for i, j in enumerate(skills)])

dfs(0, 0, [0]*m)

if not has_sol:
    print('-1')
else:
    print(min_amount)