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 itertools
N,M,X = map(int,input().split())
book =[]
for x in range(N):
    A_list =  list(map(int, input().split()))
    book.append(A_list)
conbination =[]
for i, _ in enumerate(book, 1):     
    for j in itertools.combinations(book, r=i):  # rには1、2、3と渡される
        conbination.append(j)
minn =100000000
for x in conbination:
    A = [0]*M
    m = 0
    for y in x:
        for z in range(len(y)):
            if z ==0:
                m +=y[z]
            else:
                A[z-1] +=y[z]
    if minn >m and X<=min(A):
        minn =m
        
if minn != 100000000:
    print(minn)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

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

min=10000000000000000000000000
for i in range(1,n+1):
    a=list(itertools.combinations(list(range(n)), i))
    for j in a:
        cost=0
        l2=np.zeros(m)
        for k in j:
            b=np.array(l[k][1:])
            l2+=b
            cost+=l[k][0]
            if np.all(l2>=x) and cost<min:
                min=cost

if min==10000000000000000000000000:
    print(-1)
else:
    print(min)

Submission status: Accepted

Solution code:
import itertools as it

n,m,x=map(int, input().split())
l=[]
check=[0]*(m)
ans=0
for i in range(n):
    a=list(map(int, input().split()))
    ans+=a[0]
    for j in range(m):
        check[j]+=a[j+1]
    l.append(a)

if min(check)<x:
    print('-1')
    exit()


for i in range(1,n+1):
    for p in it.combinations(range(n), i):
        #print(p)
        mon=0
        che=[0]*m
        for j in range(len(p)):
            mon+=l[p[j]][0]
            for k in range(m):
                che[k]+=l[p[j]][k+1]
        #print(che)
        if min(che)>=x:
            ans=min(ans,mon)

print(ans)

Submission status: Accepted

Solution code:
import itertools

p = list(map(int,input().split()))
N = p[0]
M = p[1]
X = p[2]

l = [[int(i) for i in input().split()] for j in range(N)]

hoge = []
kouho = list(range(1,N+1))
for i in itertools.combinations_with_replacement(kouho, N):
    hoge.append(list(set(i)))

hoge = list(map(list, set(map(tuple, hoge))))
last_val = float('inf')
flag = False

for ls in hoge:
    ls = list(set(ls))
    ans = [0] * M
    val = 0
    for a in ls:# a = [1,2]ながさM
        for ix,i in enumerate(l[a-1][1:]):
            ans[ix] += i
        val += l[a-1][0]
    b = [i for i in ans if i >= X]
    if len(b) == len(ans):
        last_val = min(last_val, val)
        flag = True

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

Submission status: Accepted

Solution code:
import itertools

n, m, x = map(int, input().split())
cost = 10**9
a = [list(map(int, input().split()))]

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

for i in range(1, n + 1): #購入する参考書の数
    for j in itertools.combinations(range(n), i): #購入する参考書の組合せ
        l = [0]*(m + 1)
        for k in j: #購入する参考書の種類をロード
            for o in range(m + 1): #1冊の参考書の情報を代入
                l[o] += a[k][o]
        cnt = 0
        for p in range(1, m + 1):
            if l[p] < x:
                break
            else:
                cnt += 1
        if cnt == m:
            cost = min(cost, l[0])


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

Submission status: Accepted

Solution code:
n, m, x = list(map(int, input().split()))
a = []
c = []
for _ in range(n):
    list_ = list(map(int, input().split()))
    c.append(list_[0])
    list_.pop(0)
    a.append(list_)
res = -1
bit = []
for i in range(2 ** n):
    tmp = [False] * n
    for j in range(n):
        if i >> j & 1:
            tmp[j] = True
    bit.append(tmp)
bit.pop(0)
cost = 10 ** 10
f = False
for i in range(2 ** n - 1):
    tmp_cost = 0
    tmp_f = True
    list_ = [0] * m
    for j in range(n):
        if bit[i][j]:
            tmp_cost += c[j]
            for k in range(m):
                list_[k] += a[j][k]
    for k in range(m):
        if list_[k] >= x:
            pass
        else:
            tmp_f = False
    if tmp_f:
        cost = min(tmp_cost, cost)
        f = True
if f:
    res = cost
print(res)

Submission status: Accepted

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

import numpy as np


N, M, X = map(int, readline().split())
C = []
A = []
ans = []

for _ in range(N):
    I = list(map(int, readline().split()))
    c = I.pop(0)
    C.append(c)
    a = np.array(I)
    A.append(a)

for b in range(2**12):
    c = 0
    U = np.zeros((M,))
    for i in range(N):
        f = b >> i & 1
        if f:
            c += C[i]
            U = U + A[i]
    if np.all(U >= X):
        ans.append(c)

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

ans = float("inf")
for i in range(1<<N):
    S = []
    for j in range(N):
        if i & (1<<j):
            S.append(j)
    
    W = [0] * M
    for s in S:
        for j in range(M):
            W[j] += A[s][j]
    
    flag = True
    for j in range(M):
        if W[j] < X:
            flag = False
            break

    if flag:
        res = 0
        for s in S:
            res += C[s]
        ans = min(ans, res)

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

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
c_list = []
a_list = []
flag = False
ans = 10**9
for i in range(n):
    tmp = list(map(int,input().split()))
    c_list.append(tmp[0])
    a_list.append(tmp[1:])
    
a_list = np.array(a_list)

for i in range(2**n):
    tmp_a = np.array([0]*m)
    tmp_c = 0
    for j in range(n):
        if ((i >> j) & 1):
            tmp_a += a_list[j]
            tmp_c += c_list[j]
    
    if min(tmp_a) >= x:
        flag = True
        if tmp_c < ans:
            ans = tmp_c
            
if flag:
    print(ans)
    
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np

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


sets = []

for i in range(n):
  sets.append(list(map(lambda x: int(x), input().split(' '))))  
sets = np.array(sets)


mincost = 10000000
maxnum = int(''.join(["1" for i in range(n)]), 2)

if not np.all((np.sum(sets[:, 1:], axis=0) >= x)):
  print(-1)
else:
  for i in range(0, maxnum+1):
    status = np.array(list(format(i, '0{}b'.format(n)))) == '1'
    used_data = sets[status]
    cost = np.sum(used_data[:, 0])
	
    if cost > mincost:
      continue
    if np.all((np.sum(used_data[:, 1:], axis=0) >= x)):
      if cost < mincost:
        mincost = cost
        next
    
  print(mincost)

Submission status: Accepted

Solution code:
import numpy
N, M, X = map(int, input().split())
status = []
for n in range(N):
    li = list(map(int, input().split()))
    status.append(li)
minimum = 10**12
def dp(depth, money, oklist):
    global minimum
    ok = oklist
    if depth == N:
        tf = True
        for m in range(M):
            if ok[m] < X:
                tf = False
        if tf:
            if money < minimum:
                minimum = money
        ok = [0]*M
        return
    dp(depth+1, money, ok)
#     for m in range(M):
#         ok[m] += status[depth][m+1]
    dp(depth+1, money+status[depth][0],ok+numpy.array([status[depth][m+1] for m in range(M)]))
oklist = numpy.array([0]*M)
dp(0, 0, oklist)
if minimum == 10**12:
  print(-1)
else:
  print(minimum)

Submission status: Accepted

Solution code:
import itertools

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

ans = []
for num_book in range(1, N + 1):
    for i in itertools.combinations(list_N, num_book):
        #print(i)
        temp = 0
        for j in range(1, M + 1):
            sum_line = sum([s[i[k]][j] for k in range(num_book)])
            if sum_line < X:
                break
            temp += 1
            if temp == M:
                score=sum([s[i[k]][0] for k in range(num_book)])
                #print(score)
                ans.append(score)
    #if len(ans) != 0:
    #    break
if len(ans)==0:
    print(-1)
else:
    #print(ans)
    print(min(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

def main():
    n,m,x=map(int,input().split())
    C=[]
    A=[]
    for _ in range(n):
        c,*a=map(int,input().split())
        C.append(c)
        A.append(a)
    ans=float('inf')
    for i in range(1<<n):
        S=[0]*m
        tmp=0
        for j in range(n):
            if (i>>j)&1==0:
                continue
            tmp+=C[j]
            B=A[j]
            for k,b in enumerate(B):
                S[k]+=b
        for s in S:
            if s<x:
                break
        else:
            ans=min(ans,tmp)
    print(-1 if ans==float('inf') else ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

import numpy as np

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

vals = np.array(vals)

import itertools

prod = []
for i in range(1, N+1):
    v = list(itertools.combinations(range(N), i))
    prod.extend(v)
    
money = 1e10

for p in prod:
    ans = np.zeros(M+1)
    
    for p_ in p:
        ans += vals[p_]
    
    flag = True
    for j in range(M):
        if ans[1+j] < X:
            flag = False
    if flag:
        if money > ans[0]:
            money = ans[0]
 
if money >= 1e10:
    print(-1)
else:
    print(int(money))

Submission status: Accepted

Solution code:
import itertools

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

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

cost = []

for i in range(1, n + 1):
    for k in itertools.combinations(range(n), i):
        c = 0
        a_list = [0] * m
        for l in k:
            c += a[l][0]
            for p in range(1, m + 1):
                a_list[p - 1] += a[l][p]
        
        if min(a_list) < x:
            continue
        else:
            cost.append(c)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N,m,x = inputs()
c = [inputs() for _ in range(N)]
cnt =[0]*(N)
ans = 10**8
for bit in range(1,1<<N):
    ans1 = 0
    cnt =[0]*(N)
    skill=[0]*m
    for j in range(N):
        if bit&1<<j:
            for i in range(1,m+1):
                skill[i-1]+=c[j][i]
            ans1+=c[j][0]
    snt =0
    for i in range(m):
        if(skill[i]>=x):
            snt+=1
        if(snt==m):
            ans=min(ans,ans1)
if ans==10**8:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

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

#%%
# n個のbit組み合わせ
flag = True
for bits in itertools.product([1, 0], repeat=n):
    skill = [0] * m # スキルは毎回初期化して良い
    cost = 0
    if all(bits):
        for r in refs:
            skill = [x + y for (x, y) in zip(skill, r[1:])]
            cost += r[0]
        if any([i < x for i in skill]): # 全部足してもだめなとき
            flag = False
            break
        else:
            ans = cost # 最大のコスト

    else:
        for i, b in enumerate(bits):
            if b == 1:
                skill = [x + y for (x, y) in zip(skill, refs[i][1:])]
                cost += refs[i][0]
        if all([i >= x for i in skill]):
            ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import sys
import copy
sys.setrecursionlimit(2**20)
N, M, X = map(int, input().split())

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

ans = float("inf")
def dfs(T, cost, i):
    global ans
    TT = copy.deepcopy(T)
    if i == N:
        flag = True
        for t in TT:
            if not t >= X:
                flag = False
        if not flag:
            return
        # print(i, TT, cost)
        ans = min(ans, cost)
        return
    dfs(TT, cost, i+1)
    for j in range(M):
        TT[j] += A[i][j]
    dfs(TT, cost+C[i], i+1)

T = [0]*M
dfs(T, 0, 0)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,M,X= map(int, input().split())
q = [list(map(int, input().split())) for _ in range(N)]
q = np.array(q)
ans = []
for j in range(2**N):
    list = []
    cost = 0
    for k in range(N):
        if (j >> k)&1:
            list.append(1)
        else:
            list.append(0)
    list = np.array(list)
    for l in range(N):
        cost +=  q[l] * list[l]
    if min(cost[1:]) >= X:
        ans.append(cost[0])
if len(ans) == 0:
    ans.append(-1)
print(min(ans))

Submission status: Accepted

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

mn = -1
for bit in range(1 << n):
    tmp = [0] * m
    t = 0
    for i in range(n):
        if (bit & (1<<i)):
            t += c[i]
            for j in range(m):
                tmp[j] += a[i][j]
    if t != 0 and (mn > t or mn == -1) and len([i for i in tmp if i >= x]) == len(tmp):
        mn = t

print(mn)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m,x=LI()
  l=[LI() for _ in range(n)]

  ans=inf
  for i in range(1<<n):
    ans_l=[0]*m
    sm=0
    for j in range(n):
      if i&(1<<j):
        for _i,y in enumerate(l[j]):
          if _i>0:
            ans_l[_i-1]+=y
        sm+=l[j][0]
    # print(ans_l)
    f=True
    for _x in ans_l:
      if _x<x:
        f=False
    if f:
      ans=min(ans,sm)

  if ans==inf:
    return -1

  return ans

# main()
print(main())

Submission status: Accepted

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

for i in range(n) :
    ca = list(map(int,input().split()));
    price[i] = ca[0];
    for j in range(m) :
        rikai[i][j] = ca[j+1];

ans = sum(price);
able = 0;
for i in range(2**n) :
    allrikai = [0]*m;
    nowprice = 0;
    for j in range(n) :
        if (i>>j)&1 :
            nowprice += price[j];
            for k in range(m) :
                allrikai[k] += rikai[j][k];
    check = 1;
    for j in range(m) :
        if allrikai[j] < x :
            check = 0;
            break;
    if check and nowprice <= ans :
        able = 1;
        ans = nowprice;

if able :
    print(ans);
else :
    print(-1);

Submission status: Accepted

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

alist = []
clist = []

for i in range(n):
  q = list(map(int,input().split()))
  alist.append(q[1:])
  clist.append(q[0])
  
total = sum(clist)
ans = float('inf')

def plus(x, y):
  return x+y


for i in range(2**n):
    money = 0 
    sum = [0]*m

    for j in range(n):
        if (i>>j)&1:
            sum = list(map(plus, sum, alist[j]))
            money += clist[j]

    for k in range(m):
      if sum[k] < x:
        break
    else:
      if ans >= money:
        ans = money

        
if ans <= total:
  print(ans)
else:
  print(-1)

Submission status: Accepted

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

for _ in range(N):
    aa_list.append(list(map(int, input().split())) )

over_set = list()
for ii in range(2 ** N):
    a_sum = [0 for _ in range(M)]
    for j in range(N):
        if (ii >> j) & 1:
            for k in range(1, M+1):
                a_sum[k-1] += aa_list[j][k]
    
    flag = True
    for k in range(M):
        if a_sum[k] < X:
            flag = False
    if flag:
        over_set.append(ii)

if len(over_set) == 0:
    print(-1)
else:
    min_val = 10**5 * N +3
    for ii in over_set:
        # print(bin(ii))
        sum_val = 0
        for j in range(N):
            if (ii >> j) & 1:
                sum_val += aa_list[j][0]
        min_val = min(min_val, sum_val)

    print(min_val)

Submission status: Accepted

Solution code:
"""    Arnab Chanda    """

from collections import defaultdict, deque
from itertools import permutations
from sys import stdin,stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy
import heapq

int_input=lambda : int(stdin.readline())
string_input=lambda : stdin.readline().split()
multi_int_input =lambda : map(int, stdin.readline().split())
multi_input = lambda : stdin.readline().split()
list_input=lambda : list(map(int,stdin.readline().split()))
string_list_input=lambda: list(string_input())
MOD = pow(10,9)+7


import itertools

n, m, k = multi_int_input()

stuff = [x for x in range(0, n)]

a = []

for i in range(n):
    b = list_input()
    a.append(b)

ans = 9999999999999999

def calculate(arr):
    ax = [0 for i in range(m+1)]
    cost = 0
    for j in arr:
        for i in range(1,m+1):
            ax[i] += a[j][i]
        cost+= a[j][0]
    for j in range(1, m+1):
        if ax[j] < k:
            return 9999999999999999
    return cost

for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        
        ans = min(ans, calculate(subset))
        # print(subset, ans)

if ans == 9999999999999999:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import sys 
try:
	sys.stdin = open('Input.txt', 'r') 
	sys.stdout = open('Output.txt', 'w')
except:
	pass

input = sys.stdin.readline

def Buy(books,threshold):
	if len(books) == 0:
		for k in threshold:
			if k<x:
				return float('inf')
		else:
			return 0
			
	thresholdnew = threshold[:]
	for k in range(m):
		thresholdnew[k] += books[0][k+1]
	return min(Buy(books[1:],threshold),books[0][0]+Buy(books[1:],thresholdnew))

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

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

ans = Buy(books,threshold)

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
book = [0] * N
total = [0] * M
point = [[] for i in range(N)]
ans = 10 ** 9

for i in range(N):
  a = list(map(int,input().split()))
  book[i] = a[0]
  point[i] = a[1:]
  for j in range(M):
    total[j] += point[i][j]

if any([i < X for i in total]):
  print(-1)
else:
  for i in range(2 ** N):
    pattern = [0] * M
    cost = 0
    for j in range(N):
      if (i >> j) & 1:
        pattern = [pattern[t] + point[j][t] for t in range(M)]
        cost += book[j]
    if all([i >= X for i in pattern]):
      ans = min(ans,cost)
  print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
price_points=[]
for i in range(n):
    line=list(map(int,input().split()))
    price_points.append(line)
sum_list=[]
for i in range(2**n):
    i=bin_str = format(i, 'b')
    # i=str(i)
    i_len=len(i)
    i_n_bit="0"*(n-i_len)+i
    sum_=0
    points=[0]*m
    for j in range(n):
        if i_n_bit[j]=="0":
            continue
        else:
            sum_+=price_points[j][0]
            for k in range(m):
                points[k]+=price_points[j][k+1]
    counter=0
    for l in range(m):
        if points[l]>=x:
            counter+=1    
    if counter==m:
        sum_list.append(sum_)
if len(sum_list)==0:
    print(-1)
else:
    print(min(sum_list))

Submission status: Accepted

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

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

ans = []
for i in pattern:
    l = [0 for j in range(m+1)]
    for j in range(n):
        if i[j]:
            for k in range(m+1):
                l[k] += lis[j][k]
    
    flag = 1
    for j in range(1, m+1):
        if l[j] < x:
            flag = 0
            break
    if flag:
        ans.append(l[0])
if not len(ans):
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
#------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
#-------------------game starts now-----------------------------------------------------
n,m,x=map(int,input().split())
e=[]
tot=999999999999999999999999999
def binary(n,ju):
    binaryNum = [0] * (ju) 
    i = 0
    while (n > 0):  
        binaryNum[i] = n % 2 
        n = int(n / 2) 
        i += 1 
    binaryNum.reverse()
    return binaryNum
for i in range(n):
    e.append(list(map(int,input().split())))
for i in range(0,2**(n)):
    ans=[0]*m
    s=binary(i,n)
    cost=0
    #print(s)
    for j in range(n):
        if s[j]==1:
            cost+=e[j][0]
            for k in range(m):
                ans[k]+=e[j][k+1]
    f=0
    for j in ans:
        if j<x:
            f=1
            break
    if f==0:
        tot=min(tot,cost)
if tot==999999999999999999999999999: 
    print(-1)
else:
    print(tot)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
ans = []
CAs = [[int(i) for i in input().split()] for j in range(N)]
for i in range(1<<N):
    rikai = [0 for k in range(M)]
    res = 0
    for j in range(N):
        if (i>>j) & 1:
            res += CAs[j][0]
            for s in range(1,M+1):
                rikai[s-1] += CAs[j][s]
    for j in rikai:
        if j<X:
            res = -1
    ans.append(res)

ans = set(ans)
ans.discard(-1)
if ans:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math
import itertools

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

  canMoney = []
  for i in range(n):
    for book_comb in itertools.combinations(books, i+1):
      sum = [0 for _ in range(m+1)]
      for book in book_comb:
        for j in range(m+1):
          sum[j] += book[j]
      
      enough = True
      for s in range(len(sum)-1):
        if sum[s+1] < x:
          enough = False
          break
      if enough:
        canMoney.append(sum[0])

  if len(canMoney) == 0:
    print('-1')
  else:
    canMoney.sort()
    print(canMoney[0])


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
sys.setrecursionlimit(150000)

N, M, X = map(int, sys.stdin.readline().split())
a = []
for i in range(N):
    a.append(inpl())
b = [0] * M
res = float("INF")
def DFS(cost, start, temp):
    global res
    if min(temp) >= X:
        res = min(res, cost)
        return res
    for i in range(start, N):
        c = temp.copy()
        d = [i + j for i, j in zip(c, a[i][1:])]
        DFS(cost + a[i][0], i + 1, d)
    return res

ans = DFS(0,0,b)
if ans != float("INF"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations

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

    row = []

    ans = 10 ** 10

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

    for k in range(1, N+1):
        co = list(combinations(row, k))

        for t in co:
            cost = 0
            skill = [0] * M
            for v in t:
                cost += v[0]
                for s in range(M):
                    skill[s] += v[s+1]

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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def m():
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split())) for _ in range(N)]
    ans = float('inf')
    for i in range(2 ** N):
        b = bin(i)[2:]
        b = b.zfill(N)
        tmp = [0] * (M + 1)
        for j, v in enumerate(b):
            if v == '0':
                continue
            tmp[0] += CA[j][0]
            for k in range(1, M + 1):
                tmp[k] += CA[j][k]
        f = 1
        for p in range(1, M + 1):
            if tmp[p] < X:
                f = 0
                break
        if f == 0:
            continue
        ans = min(ans, tmp[0])
    if ans == float('inf'):
        return '-1'
    else:
        return ans


print(m())

Submission status: Accepted

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

ans = float('inf')
for i in product([True, False], repeat=n):
    alg = [0]*m
    cost = 0
    for id, j in enumerate(i):
        c = C[id]
        a = A[id]
        if j:
            for k in range(m):
                alg[k]+=a[k]
            cost+=c
    if min(alg)>=x: ans=min(ans, cost)
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
Line = [int(s) for s in input().split()]
n,M,X = Line[0],Line[1],Line[2]

ans = -1
money = []

item = [0]*n
# print(item)
# print(X)


for i in range(n):
    item[i] = [int(s) for s in input().split()]
# print(item)

for i in range(2 ** n):
    bag = []
    algos = [0]*M
    # print("pattern {}: ".format(i), end="")
    total = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(item[j][0])  # フラグが立っていたら bag に果物を詰める
            total += item[j][0]  # 買い物累計額にも加算
            for x in range(M):
                algos[x] += item[j][x+1]
    # print(algos)
            
    if (all(elem >= X for elem in algos)):
        # print(total, bag,algos)
        ans = 1
        money.append(total)
if ans == 1:
    print(min(money))
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

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

N_list = list(range(N))

price_list = []
point_list = []

x = []

for i in range(N):
  my_list = list(map(int, input().split()))
  price_list.append(my_list[0])
  point_list.append(my_list[1:])
  x.append(list(combinations(N_list, i+1)))

my_np = np.array(point_list)

ans = None

for i in x:
  for j in i:
    check_price = 0
    check_np = np.zeros(M)
    for k in j:
      check_price += price_list[k]
      check_np += my_np[k]
    if min(check_np) >= X:
      if ans is None:
        ans = check_price
      else:
        ans = min(check_price,ans)

if ans is None:
  ans = -1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N, M, X = map(int, input().split())
CAs = [[int(n) for n in input().split()] for _ in range(N)]

MAX = 10 ** 5 * 12 + 1
min_ = MAX

for i in range(1, N + 1):
    for cas in combinations(CAs, i):
        rikai = [0] * M
        kakaku = 0
        for ca in cas:
            for j in range(M):
                rikai[j] += ca[j + 1]
            kakaku += ca[0]
        if len(list(filter(lambda x: x < X, rikai))) == 0:
            min_ = min(min_, kakaku)
if min_ == MAX:
    print('-1')
else:
    print(min_)