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:
from itertools import combinations
 
N, M, X = list(map(int,input().split()))
A = []
for i in range(N):
  A.append(list(map(int,input().split())))
sum = []
subsets=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        subsets.append(list(c))
 
for i in subsets:
  tmp = [0]*(M+1)
  if len(i) == 1:
    sum.append(i[0])
  elif len(i) == 0:
    sum.append([0]*(M+1))
  else:
    for j in i:
      tmp = list(map(lambda a,b: a + b, tmp,j))
    sum.append(tmp)
    
min_price = 10000000000
 
for i in sum:
  t = 0
  for j in range(len(i)):
    if j==0:
      pass
    elif X > i[j]:
      t = 1
      break
  if t == 0:
    min_price = min(min_price, i[0])
 
if min_price == 10000000000:
  print(-1)
else:
  print(min_price)

Submission status: Accepted

Solution code:
nmx = [int(x) for x in input().split()]
n = nmx[0]
m = nmx[1]
x = nmx[2]

lis = []
for i in range(0,n):
    lis.append([int(x) for x in input().split()])


def dp(i, cost, scores):
    if i == n:
        ok = True
        for j in range(0, m):
            if scores[j] < x:
                ok = False
        if ok == True:
            return(cost)
        else:
            return(999999999999)
    else:
        newCost = cost + lis[i][0]
        newScores = [0]*m
        for j in range(0,m):
            newScores[j] = scores[j] + lis[i][j+1]
        return(min([dp(i+1,cost,scores), dp(i+1,newCost,newScores)]))

temp = [0]*m

yeet = (dp(0,0,temp))
if yeet == 999999999999:
    print(-1)
else:
    print(yeet)

Submission status: Accepted

Solution code:
import itertools
n, m, x = list(map(int, input().split()))
books=[]
results=[]
for i in range(n):
    books.append(list(map(int, input().split())))
# 全ての本を買ってもXwo満たせないアルゴリズムがあるか検査
for i in range(m):
    skill=0
    for j in books:
        skill+=j[i+1]
    if skill<x:
        print(-1)
        exit()

# 本の組み合わせをためす
index=[]
for i in range(n):
    index.append(i)
patarns=[]
for i in range(1,n+1):
    patarns.append(itertools.combinations(index,i))
    #print(list(a))

# 全パターン検査
for patarn in patarns:
    #flg=True
    # ある本の組み合わせの時検査
    for bk_indexies in patarn:
        # すべてのアルゴリズム
        flg=True
        for arg in range(m):
            point=0
            money=0
            for bk_index in bk_indexies:
                # アルゴリズムargの合計得点
                point+=books[bk_index][arg+1]
                money+=books[bk_index][0]
            #print(arg,money,point)
            if point<x:
                flg=False
        if flg:
            #print(money,list(patarn))
            results.append(money)
#print(results)
print(min(results))

Submission status: Accepted

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

ans=float("inf")
for i in range(2**N):
    a=[0]*M
    checked=[0]*M
    money=0
    cnt=0
    for j in range(N):
        if i%2==1:
            for k in range(M):
                a[k]+=A[j][k]
                if a[k]>=X and checked[k]==0:
                    cnt+=1
                    checked[k]+=1
            money+=cost[j]
        i//=2
    if cnt==M:
        ans=min(ans,money)

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

Submission status: Accepted

Solution code:
import sys
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m,x=mp()
l=[lmp() for i in range(n)]
ans=[]
for i in range(2**n):
    b=bin(i)[2:]
    c=b.zfill(n)
    q=[0]*(m+1)
    for k in range(n):
        if c[k]=="0":
            for j in range(0,m+1):
                q[j]+=l[k][j]



    ch=0
    for j in range(1,m+1):
        if q[j]<x:
            ch=1
    if ch==0:
        ans.append(q[0])
if len(ans)==0:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m, x = map(int, input().split())
    ca = [list(map(int, input().split())) for _ in range(n)]
    min_ans = 10 ** 20
    max_count = 0
    for i in range(2 ** n):
        ii = list(format(i, 'b').zfill(n))
        sum_a = [0] * m
        ans = 0
        for j in range(n):
            if ii[j] == '1':
                c, *a = ca[j]
                ans += c
                for k in range(m):
                    sum_a[k] += a[k]
        check = True
        for j in range(m):
            if sum_a[j] < x:
                check = False
        if check and min_ans > ans:
            min_ans = ans

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
from collections import deque
import itertools

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

li = deque()

sum = -1
ans = 0
for i in range(n):
    li.append(list(map(int, input().split())))

for i in range(1,n+1):
    for v in itertools.combinations(li, i):
        ok = True
        for j in range(1,m+1):
            ans = 0
            for k in v:
                ans += k[j]
                if ans >= x:
                    break
            if ans < x:
                ok = False
                break

        if ok == True:
            s=0
            for j in range(i):
                s+=v[j][0]
            if sum > s or sum == -1:
                sum=s


print(sum)

Submission status: Accepted

Solution code:
from itertools import combinations

def skill(m, l, x):
    ans = pow(10, 9)
    rikai = [0 for _ in range(m)]

    for i in range(n):
        cl = combinations(range(n), i+1)
        for c in cl:
            cost = 0
            rikai = [0 for _ in range(m)]
            for j in c:
                cost += l[j][0]
                for k in range(m):
                    rikai[k] += l[j][k+1]
            flag = 0
            for k in range(m):
                if rikai[k] < x:
                    flag = 1
                    break
            if flag == 0 and cost < ans:
                ans = cost
            # print(c, cost, rikai)
    if ans != pow(10, 9):
        print(ans)
    else:
        print(-1)

n, m, x = [int(i) for i in input().split()]
l = []
for _ in range(n):
    l.append([int(i) for i in input().split()])

skill(m, l, x)

Submission status: Accepted

Solution code:
import itertools
lis=list(map(int,input().split()))
N=lis[0]
M=lis[1]
X=lis[2]
book=[[0]*(M+1)]*N
Cost=[]
for i in range(N):
    book[i]=list(map(int,input().split()))
buy=list(itertools.product('YN', repeat=N))
for i in buy :
    Buy=list(i)
    rikai=[0]*M
    cost=0
    for j in range(N):
        if(Buy[j]=="Y"):
            cost+=book[j][0]
            rikai=[x+y for (x, y) in zip(rikai,book[j][1:M+1])]
    if(min(rikai)>=X):
        Cost.append(cost)
if(len(Cost)>=1):
    print(min(Cost))
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
text = [list(map(int, input().split())) for _ in range(n)]
ans = 10**9
for bit in range(1<<n):
    skills = [0]*m
    yen = 0
    for i in range(n):
        if (bit>>i)&1:
            yen += text[i][0]
            for j in range(m):
                up = text[i][j+1]
                skills[j] += up
    for k in range(m):
        if skills[k] < x:
            break
    else:
        ans = min(yen,ans)
else:
    if ans == 10**9:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
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, 13):
    for v in itertools.combinations(book, i):
        l = np.array([0]*(M+1))
        flag = True
        for ele in v:
            l += np.array(ele)
        l = list(l)
        for j in range(1, len(l)):
            if l[j] < X:
                flag = False
        if flag:
            ans = min(ans, l[0])
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools
def c167(n, m, x, cali):

    ans = 10**8
    skill = [0]*m
    califlag = [True]*n

    for i in cali:
        for w in range(m):
            skill[w] += i[w+1]

    for i in skill:
        if i < x:
            return -1
    for i in range(1, n+1):
        itelist = list(itertools.combinations(range(n),i))
        for w in itelist:
            countans = 0
            countskill = [0]*m
            flag = True
            for q in w:
                countans += cali[q][0]
                for g in range(m):
                    countskill[g] += cali[q][g+1]
            for q in countskill:
                if q < x:
                    flag = False
            if flag:
                ans = min(ans, countans)

    return ans

def main():
    n, m, x = map(int, input().split())
    cali = [list(map(int, input().split()))for i in range(n)]
    print(c167(n, m, x, cali))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

min_cost = 9999999999999999
for i in range(1, n + 1):
    for i in itertools.combinations(range(n), i):
        tmp = sum([ np.asarray(l[k]) for k in i])
        cost = tmp[0]
        min_alg = min(tmp[1:])
        if min_alg >= x:
            if min_cost > cost:
                min_cost = cost
if min_cost == 9999999999999999:
    print('-1')
else:
    print(min_cost)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

def get_min_c(c, a, n, m, x, sum_c, sum_a, min_c, now_i):
    for i in range(now_i, n):
        if np.all(sum_a + a[i] >= x):
            if sum_c + c[i] < min_c or min_c == 0:
                min_c = sum_c + c[i]
        else:
            min_c = get_min_c(c, a, n, m, x, sum_c + c[i], sum_a + a[i], min_c, i + 1)

    return min_c


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

c = np.empty((n), dtype='int')
a = np.empty((n, m), dtype='int')
for i in range(n):
    tmp = input().split()
    c[i] = int(tmp[0])
    a[i] = tmp[1:]

max_a = np.zeros((m), dtype='int')
max_c = 0
for i in range(n):
    max_a += a[i]
    max_c += c[i]

if np.any(max_a < x):
    min_c = -1
else:
    min_c = get_min_c(c, a, n, m, x, 0, 0, 0, 0)
    
print(min_c)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M, X  = [int(x) for x in stdin.readline().rstrip().split()]

CA = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

knowledge_list = [[0 for _ in range(M)]]
money_list = [0]

for i in range(N):
    C = CA[i][0]
    A = CA[i][1:]

    # 購入する場合
    tmp2 = []
    for i, knowledge in enumerate(knowledge_list):
        tmp = []
        for k in range(len(knowledge)):
            tmp.append(knowledge[k] + A[k])
        
        tmp2.append(tmp)
        money_list.append(money_list[i]+C)

    knowledge_list = knowledge_list + tmp2

ans = INF
for i in range(len(money_list)):
    if min(knowledge_list[i]) >= X:
        ans = min(ans, money_list[i])

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

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

price = []
algo = []

for i in range(N):
  l = list(map(int, input().split()))
  price_var = l[0]
  price.append(price_var)
  l.pop(0)
  algo.append(l)

A = []
B = []
for i in range(N):
  L = list(itertools.combinations(price,i+1))
  L2 = list(itertools.combinations(algo,i+1))
  for j in range(len(L)):
    A.append(sum(L[j]))
    B.append(L2[j])

d = zip(A, B)
d = sorted(d)
ans = []
for i in range(len(d)):
  R = [0]*M
  R = np.array(R)
  for j in range(len(d[i][1])):
    R = R + np.array(d[i][1][j])
    if min(R) >= X:
      ans.append(d[i][0])

if len(ans) >= 1:
  print(min(ans))
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import combinations
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N, M, X = MII_split()

books = []
# prices = []
for i in range(N):
    book = LII_split()
    # prices.append(book[0])
    books.append(book)

# books = sorted(books.items(), key=lambda x: sum(x[1]), reverse=True)
# chosen_books = []
# is_chosen = [False for _ in range(N)]
price = 0
min_price = -1
for i in range(N):  # i = 選ぶ本の個数-1

    for tmp_books in combinations(books, i + 1):
        algo_skills = np.array([0 for _ in range(M)])
        price = 0
        for skills in tmp_books:
            algo_skills += np.array(skills[1:])
            price += skills[0]
        if np.all(algo_skills >= X):
            if min_price == -1 or price < min_price:
                min_price = price

print(min_price)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M,X=map(int,input().split())

CA=[list(map(int, input().split())) for i in range(int(N))]
CA_low_cost=float('inf')
for i in range(N):
    CA_comb=list(itertools.combinations(CA,N-i))
    for comb in CA_comb:
        comb_ls=np.array(comb)
        comb_sum=np.sum(comb_ls,axis=0)
        if list(filter(lambda x:x<X ,comb_sum[1:]))==[]:
            if CA_low_cost>comb_sum[0]:
                CA_low_cost=comb_sum[0]
if CA_low_cost==float('inf'):
    print(-1)
else:
    print(CA_low_cost)

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int, input().split())
ca = [list(map(int, input().split())) for i in range(n)]
ca.sort(key=lambda x:x[0])

ans=[0]*(m+1)
for i in range(n):
    for j in itertools.combinations(ca, i+1):
        p=[0]*(m+1)
        for k in range(m+1):
            for value in range(len(j)):
                p[k] += j[value][k]
        kari_ans = [i for i in p[1:] if i >= x]
        if len(kari_ans) >= m and (ans[0] == 0 or ans[0] > p[0]):
            ans = p
if ans[0] != 0:
    print(ans[0])
else:
    print("-1")

Submission status: Accepted

Solution code:

from itertools import combinations
n, m, x = map(int, input().split())

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

ans = 10**10
for i in range(1, n+1):
    for j in combinations(a, i):
        sm = list(map(sum, zip(*j)))
        if len(list(filter(lambda y: y >= x, sm[1:]))) >= m:
            if ans >= sm[0]:
                ans = sm[0]

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

Submission status: Accepted

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

ans = 10 ** 7
for i in range(2 ** N):
  abi = [0] * M
  money = 0
  for j in range(N):  # このループが一番のポイント
    #print(i, j)
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
        
        money += C[j][0]
        for k in range(M):
          abi[k] += C[j][k + 1]
          
  #print(abi, money)
  if min(abi) >= X:
    ans = min(ans, money)
  #print("A")
  
if ans == 10 ** 7:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int,input().split())
ca = []
for i in range(n):
    cakari = list(map(int,input().split()))
    ca.append(cakari)
ans = 1000000000000
for i in range(2**n):
    i = format(i, 'b')
    izero = i.zfill(n)
    utd = [0 for i in range(m+1)]
    for j in range(n):
        if izero[j] == '1':
            for k in range(m+1):
                utd[k] += ca[j][k]
    judge = True
    for l in range(m):
        if utd[l+1] < x:
            judge = False
    if judge == True and ans > utd[0]:
        ans = utd[0]
    
if ans != 1000000000000:
    print(ans)
else:
    print('-1')

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, M, X = map(int, input().split())
    CA = np.array([np.array([int(v) for v in input().split()]) for _ in range(N)])

    def dp(i, a):
        if np.all(a>=X):
            return 0
        if i >= N:
            return -1
        purchased = dp(i + 1, a+CA[i][1:])
        unpurchased = dp(i + 1, a[:])
        if purchased != -1:
            purchased += CA[i][0]
            if unpurchased != -1:
                return min(purchased, unpurchased)
            else:
                return purchased
        else:
            return unpurchased
    
    print(dp(0, np.zeros(M, dtype=np.int32)))


if __name__ == '__main__':
    main()

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())))
#print(CA)

m=[i+1 for i in range(N)]

from itertools import combinations

minmoney=float('inf')
for k in range(N):
  for i in combinations(m,k+1):
      #print(i)
      money=0
      r=[0]*M
      for j in range(len(i)):
          money+=CA[i[j]-1][0]
          #print("-------")
          #print(r)
          #print(CA[i[j]-1][1:])
          
          r=np.array(r)+np.array(CA[i[j]-1][1:])
          #print(CA[i[j]-1][0])
      #print(r)   
      n = sum(x>=X for x in r)
      #print(n)
      if n==M and money<minmoney:
          minmoney=money
if minmoney==float('inf'):
  print(-1)
else:
  print(minmoney)

Submission status: Accepted

Solution code:
import itertools

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

combi = list()
for i in range(N):
    combi += itertools.combinations(range(N), i+1)

ok = list()
for books in combi:
    money = 0
    rikai = [0] * M
    for book in books:
        money += C[book]
        for i in range(M):
            rikai[i] += A[book][i]

    for r in rikai:
        if r < X:
            break
    else:
        ok.append(money)

result = min(ok) if len(ok) != 0 else -1
print(result)

Submission status: Accepted

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

onedan = []

for j in range(1,N+1):
    #本の全組み合わせリスト(1個からN個まで)
    CCj = list(itertools.combinations(C,j))

    for k in range(len(CCj)):
        rikai = True
        for l in range(1,M+1):
            #各ゴリズムの理解力(rikaipower)判定
            rp = sum([CCj[k][m][l] for m in range(j)])
            if rp < X:
                rikai = False
                break
        if rikai:
            onedan.append(sum([CCj[k][m][0] for m in range(j)]))
if onedan == []:
    print(-1)
else:
    print(min(onedan))

Submission status: Accepted

Solution code:
import numpy as np

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

# 参考書の値段
C_list = []

# 参考書が持つ理解度を上げる能力
A_list = []

for i in range(N):
    C_A_list = list(map(int, input().split()))
    C_list.append(C_A_list[0])
    A_list.append(C_A_list[1:])

A_list = np.array(A_list)

is_use_list = [False] * N

min_value = -1
understand_list = [0] * M
understand_list = np.array(understand_list)
c_total = 0

def dfs(i):

    global c_total
    global understand_list
        
        
    if min(understand_list) >= X:

        global min_value
        if min_value == -1 or c_total < min_value:
            min_value = c_total

    if i >= N:
        return


    is_use_list[i] = True
    understand_list = understand_list + A_list[i]
    c_total += C_list[i]
    dfs(i + 1)
    is_use_list[i] = False
    understand_list = understand_list - A_list[i]
    c_total -= C_list[i]
    dfs(i + 1)

dfs(0)

print(min_value)

Submission status: Accepted

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

C = list()
A = list()

for i in range(N):
  L = list(map(int,input().split()))
  C.append(L[0])
  A.append(L[1:])
now_cost = 10**10

import itertools

for cm in itertools.product([0,1], repeat=N):
  c = 0
  a = [0 for i in range(M)]
  for i, j in enumerate(cm):
    if j == 1:
      flag = 1
      c += C[i]
      for k in range(M):
        a[k] += A[i][k]
        if a[k] < X:
          flag = 0
      if flag == 1:
        now_cost = min(now_cost, c)
        continue
      
if now_cost == 10**10:
  print(-1)
else:
  print(now_cost)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
n,m,x=map(int, input().split())

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

ans = 10**9
for i in range(1,n+1):
    for comb in combinations(S,i):
        #print(comb)
        tmp = np.array([0]*m)
        
        cost = 0
        for s in comb:
            tmp += np.array(s[1:])
            cost += s[0]
        #print(tmp)
        #print(cost)
        cnt = 0
        for t in tmp:
            if t >= x: cnt+=1
        #print(cnt,m)
        if cnt == m:
            ans = min(ans,cost)
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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


#print(M_list)
cost = 0
C_list = []
for _ in range(N):
    C = [int(x) for x in input().split()]
    C_list.append(C)
#print(C_list)
ans = []

for i in range(1<<N):
    cnt = 0
    M_list = [0 for x in range(M+1)] 
    for j in range(N):
        for k in range(M):
            if (i>>j)&1 == 1:
                M_list[k+1] += C_list[j][k+1]
                M_list[0] += C_list[j][0]
                #if M_list[k+1] >= X:
    #print(M_list)
    
    cnt = 0
    for p in range(M):
        #cnt = 0
        if M_list[p+1] >= X :
            cnt += 1
    if cnt == M :
        ans.append(M_list[0])
    
if ans == []:
    print(-1)
else:print(int(min(ans)/M))

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

ans = -1

num_list.sort(key=lambda x: x[0])

result = []
for n1 in range(1,len(num_list)+1):
    for conb in itertools.combinations(num_list, n1):
        result.append(np.sum(conb, axis=0))

result.sort(key=lambda x: x[0])

for r in result:
    if min(r[1:]) >= x:
        ans = r[0]
        break

print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
a_list = []
for i in range(n):
	targets = list(map(int, input().split()))
	a_list.append(targets)
r_list = []
for i, _ in enumerate(a_list, 1):     
	for j in itertools.combinations(a_list, r=i):
		targets = [0] * (m+1)
		for t in j:
			k = 0
			for target in t:
				targets[k] += target
				k += 1
		pop_list = targets[1:m+1]
		if min(pop_list) >= x:
			r_list.append(targets)
if len(r_list) == 0:
	print(-1)
else:
	result = sorted(r_list, key=lambda x: x[0])
	print(result[0][0])

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq

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

c=np.array([list(map(int,input().split())) for _ in range(n)])
kumi=[i for i in range(n)]
ans=float("inf")
for k_n in range(n+1):
    t=itertools.combinations(kumi, k_n)
    for each in t:
        cal=c[each,:].sum(axis=0)
        if min(cal[1:])>=x:
            ans=min(cal[0],ans)
if ans==float("inf"):
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, M, X = In.ints()

cost = [0]*N
ach = [[0 for i in range(M)] for j in range(N)]

for i in range(N):
    ine = In.ints()
    cost[i] = ine[0]
    ach[i] = ine[1::]

res = 99999999999


for i in range(N):            
    for comb in itertools.combinations([i for i in range(N)], i+1):        
        cur_cost = 0
        accum = [0]*M

        for el in comb:
            cur_cost+=cost[el]

            for j in range(M):
                accum[j] += ach[el][j]

            if all([x>=X for x in accum]):
                found=True
                res = min(res, cur_cost)
                break


if res == 99999999999:
    Out.int(-1)
else:
    Out.int(res)

######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
lst = []
for _ in range(n):
    lst.append(list(map(int, input().split())))
ans = 10**50
flg = 0

for i in range(2 ** n):
    achv = [0] * (m + 1)
    for j in range(n): 
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            achv = list(map(lambda x,y: x+y, achv, lst[j]))# フラグが立っていたら bag に果物を詰める
    if len([_ for _ in achv[1:m+1] if _ >= x]) == m and achv[0] > 0:

        ans = min(ans, achv[0])
        flg = 1

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

Submission status: Accepted

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

ans=100000000000000
for i in range(2**n):
    id_str=str(bin(i))[2:]
    plus=['0']*(n-len(id_str))
    plus_str=''
    for j in range(len(plus)):
        plus_str+=plus[j]
    id = plus_str+id_str
    m_sum=[0]*m
    c_sum=0
    for j in range(n):
        if id[j]=='1':
            for k in range(m):
                m_sum[k]+=a[j][k]
            c_sum+=c[j]
    if min(m_sum)>=x:
        if c_sum<ans:
            ans=c_sum

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

Submission status: Accepted

Solution code:
from itertools import combinations
n , m ,x = map(int , input().split())
arr = [list(map(int , input().split())) for i in range(n)]
ans = 10**10
for i in range(1,n+1):
	for k in combinations(arr , i):
		#print(k,i,n)
		a = [0]*m
		#print(k)
		f = 1
		cost = 0
		for ele in k:
			#print(ele)
			cost += ele[0]
			for e in range(1,m+1):
				a[e-1] += ele[e]
		for _i in a:
			if _i < x:
				f = 0
				break
		if f : ans = min(ans , cost)
print(ans if ans < 10**10 else -1)

Submission status: Accepted

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

import itertools
import numpy as np


def main():
    N, M, X = map(int, input().split())
    CA = np.array([list(map(int, input().split())) for _ in range(N)])
    C = np.array(CA[:, 0])
    A = np.array(CA[:, 1::])

    if min(np.sum(A, axis=0)) < X:
        print('-1')
        return

    pattern = []
    for i in range(1, N + 1):
        pattern.extend(list( itertools.combinations(list(range(N)), i) ))

    kumiawase = []
    for p in pattern:
        cost = sum([C[_] for _ in p])
        x = [A[_] for _ in p]
        kumiawase.append( (cost, x) )
        pass
    kumiawase = sorted(kumiawase, key=lambda x: x[0])

    for k in kumiawase:
        zz = k[1]
        if min(np.sum(zz, axis=0)) >= X:
            print(k[0])
            return

    print('-1')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
N,M,X=map(int,input().split())
x=[]
for i in range(N):
    y=list(map(int,input().split()))
    x.append(y)
def can(i,X):
    z=np.sum(i, axis=0)
    if X<=min(z[1:]):
        return z[0]
    else:
        return -1
y=[]
for i in range(1,len(x)+1):
    y.extend(list(combinations(x, i)))
A=[]
for i in y:
    z=can(i,X)
    if z==-1:
        continue
    A.append(z)
if len(A)==0:
    print(-1)
else:
    print(min(A))

Submission status: Accepted

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

v=[]
l=[]
for i in range(n):
    c=list(map(int,input().split()))
    v.append(c[0])
    l.append(c[1:])
    
ans=sum(v)
for i in range(2**n):
    total=0
    flag=True
    r=[0]*m
    for j in range(n):
        if (i >> j) & 1:
            total += v[j]
            for k in range(m):
                r[k] += l[j][k]
    
    for i in r:
        if i < x:
            flag=False
            break
    if flag:
        ans = min(ans,total)
    
if not flag:
    print(-1)
    exit()
print(ans)