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 math
import itertools

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

_min = float("inf")

for i in range(n):
    for j in list(itertools.combinations(range(n), i + 1)):
        _sum = [0 for _ in range(m)]
        cost = 0
        for jj in j:
            cost += li[jj][0]
        for l in range(1, m + 1):
            for k in j:
                _sum[l - 1] += li[k][l]
        flg = True
        #print(_sum)
        for w in _sum:
            if x > w:
                flg = False
                break
        if flg:
            _min = min(_min, cost)
        # for k in range(j):
        #     print(li[])
        #     _sum += 1

if math.isinf(_min):
    print(-1)
else:
    print(_min)

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)]
all_list = list(itertools.product([0,1], repeat=n))
ans_flag = False

final_answer = float("inf")
for i in range(len(all_list)):
  anslist = [0]*(m+1)
  anscost = 0
  flag = True
  for j in range(n):
    if all_list[i][j] == 1:
      anscost += ca[j][0]
      for k in range(1,m+1):
        anslist[k] += ca[j][k]
  # print(anslist)
  for l in range(1,m+1):
    if anslist[l] < x:
      flag = False
  if flag:
    ans_flag = True
    
    final_answer = min(final_answer,anscost)

if ans_flag:
  print(final_answer)
else:
  print("-1")

# for bit in range(2**m):
#   for i in range(n):
#     if (bit >> i) & 1:
#       anscost += ca[i][0]

Submission status: Accepted

Solution code:
def mysum(A, B):
    C = [0] * len(A)
    for i in range(len(A)):
        C[i] = A[i] + B[i]
    return C


def mytruthy(A, X):
    for a in A:
        if a < X:
            return False
    return True


def c():
    N, M, X = map(int, input().split())
    R = {}
    costs = []

    for i in range(N):
        V = list(map(int, input().split()))
        if i == 0:
            R['0'*N] = [0] * (M + 1)
            R['1' + '0'*(N-1)] = V
            if mytruthy(V[1:], X):
                costs.append(V[0])
        else:
            newR = {}
            for k in R.keys():
                k2 = k[:i] + '1' + k[i+1:]
                newR[k2] = mysum(R[k], V)
                if mytruthy(newR[k2][1:], X):
                    costs.append(newR[k2][0])
            R.update(newR)

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


##########
if __name__ == "__main__":
    c()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

N, M, X = map(int, input().split())
cost_list = []
A_list_list = []
for i in range(N):
    input_list = list(map(int, input().split()))
    cost_list.append(input_list[0])
    A_list_list.append(input_list[1:])
max_cost = sum(cost_list)

def dfs(bool_list, min_cost):
    if len(bool_list) == N:
        cost = 0
        rikaido_list = [0 for k in range(M)]
        for i in range(N):
            if bool_list[i] :
                cost += cost_list[i]
                for j in range(M):
                    rikaido_list[j] += A_list_list[i][j]
        if min(rikaido_list)>=X:
            min_cost = min(min_cost, cost)
        return min_cost
    for b in [True, False]:
        bool_list.append(b)
        min_cost = min(min_cost, dfs(bool_list, min_cost))
        bool_list.pop()
    return min_cost

def main():
    min_cost = max_cost + 1
    min_cost = dfs([], min_cost)
    if min_cost > max_cost:
        min_cost = -1
    print(min_cost)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import add
n,m,x=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]

ans=float('inf')
for i in range(2**n):
  c=0
  s=[0]*m
  for b in range(n):
    if i>>b&1:
      c+=l[b][0]
      for j in range(m):
        s[j]+=l[b][j+1]
  if all([e>=x for e in s]):
    ans=min(ans,c)
if ans==float('inf'):
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
pA = [0]*N
for i in range(N):
    pA[i] = list(map(int,input().split()))
C = [0]*12
A = [0]*12
for i in range(N):
    C[i] = pA[i][0]
    A[i] = pA[i][1:]
minprice = sum(C)+1


for i1 in range(2):
    for i2 in range(2):
        for i3 in range(2):
            for i4 in range(2):
                for i5 in range(2):
                    for i6 in range(2):
                        for i7 in range(2):
                            for i8 in range(2):
                                for i9 in range(2):
                                    for i10 in range(2):
                                        for i11 in range(2):
                                            for i12 in range(2):
                                                point = 0
                                                tasei = [0]*M
                                                price = 0
                                                itati = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12]
                                                for j in range(N):
                                                    price += itati[j]*C[j]
                                                    for k in range(M):
                                                        tasei[k] += itati[j]*A[j][k] 
                                               
            
                                                for i in range(M):
                                                    if tasei[i]>=X:
                                    
                                                        if i == M-1:
                                                            point = 1
                                                    else:
                                                        break
                                                    
                                                       
                                                
                                                if price < minprice and point == 1:
                                                    minprice = price
                                                  
if minprice == sum(C)+1:
    print(-1)
else:
    print(minprice)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import itertools

# スペース区切りの整数の入力
N, M, X = map(int, input().split())
# 文字列の入力
#s = input()
#開業されたN個要素を受け付ける
input_list = [list(map(int, input().split())) for i in range(N)]

#print(input_list)
ans = -1
flg=1
for i in range(N+1):
    if i ==0:
        continue
    c = list(itertools.combinations(input_list, i))
    #print(c)
    flg=1
    for l in c:
        #print(l)
        flg=1
        for j in range(M):
            sum=0
            for k in range(i):
                #print(l[k][j+1])
                sum=sum+l[k][j+1]
            #print(sum)
            if sum<X:
                flg=0
        if flg==1:
            sum=0
            for j in range(i):
                sum=sum+l[j][0]
            if ans==-1:
                ans = sum
            elif sum<ans:
                ans = sum
        #print(ans)


print(ans)

Submission status: Accepted

Solution code:
import itertools


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

INF = 10 ** 5 * 12 + 1
min_amount = INF
for i in range(1, N + 1):
    combinations = itertools.combinations(range(N), i)

    for combination in combinations:
        understanding_list = [0] * M
        amount = 0
        for i in combination:
            for j in range(1, len(CA[i])):
                understanding_list[j - 1] += CA[i][j]
            amount += CA[i][0]

        # print(understanding_list)
        is_reached = all([understanding >= X for understanding in understanding_list])
        if not is_reached: continue

        min_amount = min(amount, min_amount)

answer = -1 if min_amount == INF else min_amount

print(answer)

Submission status: Accepted

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

import itertools
for i in range(1,n+1):
    c = list(itertools.combinations(CA,i))
    for j in c:
        com.append(j)
        
ans = 12*(10**5)+1
        
for i in com:
    res = [0]*(m+1)
    
    for j in range(len(i)):
        ca = i[j]
        
        for k in range(m+1):
            res[k] += ca[k]
            
    ok = 0        
    for j in res[1:]:
        if j >= x:
            ok += 1
            
        if ok == m:
            ans = min(ans,res[0])

if ans == 12*(10**5)+1:
    ans = -1
            
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as c

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

g = list(range(1, n + 1))

h = -1
for i in range(1, n + 1):
	for p in c(g, i):
		s = 0
		r = [0] * m
		for v in p:
			s += arr[v-1][0]
			for k in range(m):
				r[k] += arr[v-1][k+1]
		u = 1
		for v in r:
			if v < x:
				u = 0
		if u:
			if h == -1:
				h = s
			else:
				h = min(h, s)
print(h)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(n)]
import itertools
max_=-1
for i in range(n):
    c_list = list(itertools.combinations(c, i+1))
    for j in c_list:
        d=[0]*(m+1)
        for k in j:
            d = [x+y for (x,y) in zip(d,k)]
        f=1

        for l in range(1,m+1):

            if d[l] < x:
                f=0
                break

        if f==1:
            if max_ ==-1:
                max_ = d[0]
            elif d[0] < max_:
                max_ = d[0]

print(max_)

Submission status: Accepted

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

ans = 1000000000
for i in range(1,n+1):
    for v in itertools.combinations(ab, i):
        memo = [0]*(m+1)
        for k in v:
            for l in range(m+1):
                memo[l] += k[l]
            flag = True
            for o in range(1,m+1):
                if memo[o] < x:
                    flag = False
        if flag:
            ans=min(memo[0],ans)

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

Submission status: Accepted

Solution code:
import numpy as np

n,m,x = [int(i) for i in input().split()]
costs =[]
maa = 1000000000000000000000000000
ans = maa

for i in range(n):
    a = [int(i) for i in input().split()]
    costs.append(a)
    
for i in range(1,2**n+1):
    cost = 0
    c = 0
    sums = [0] * m
    use_index=[]
    for j in range(n):
        if i%2==1:
            use_index.append(j)
        i >>= 1
    
    for v in use_index:
        c += costs[v][0]        
        for j in range(m):
            sums[j] += costs[v][j+1]
            
    judge=True
    for j in range(m):
        if sums[j]<x:
            judge=False
            break
    
    if judge:
        ans = min(ans, c)

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

Submission status: Accepted

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

import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys


def S():
    return sys.stdin.readline().rstrip()


def I():
    return int(sys.stdin.readline().rstrip())


def LI():
    return list(map(int, sys.stdin.readline().rstrip().split()))


def LS():
    return list(sys.stdin.readline().rstrip().split())


def num2ary(n, num):
    ret = [0] * n
    x = 2 ** (n - 1)
    for i in range(n):
        if x <= num:
            num = num - x
            ret[i] = 1
        else:
            ret[i] = 0
        x = x / 2
    return ret


def main():
    n, m, x = LI()
    # print(n, m, x)
    c = []
    a = [[0] * m] * n
    # print(a)
    for i in range(n):
        z = LI()
        # print(z)
        c.append(z[0])
        # print(c)
        a[i] = z[1:]
        # print(a)
    cmin = 9999999999
    for i in range(2 ** n):
        csum = 0
        asum = [0] * m
        ary = num2ary(n, i)
        for j in range(n):
            if ary[j] == 1:
                csum = csum + c[j]
                for k in range(m):
                    asum[k] = asum[k] + a[j][k]
        # print("xxx", i, csum, asum)
        ok = 1
        for i in range(m):
            if asum[i] < x:
                ok = 0
                break
        if ok == 1 and csum < cmin:
            cmin = csum
            # print("yyy", i)
    if cmin >= 9999999999:
        print(-1)
    else:
        print(cmin)
    # N = I()
    # A = [LI() for _ in range(N)]


main()

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
c=[0]*n
a=[0]*n
for i in range(n):
  tmp=list(map(int,input().split()))
  c[i]=tmp[0]
  a[i]=tmp[1:]
price=sum(c)+1
for i in range(2**n):
  now_p=0
  score=np.zeros(m)
  
  for j in range(n):  # このループが一番のポイント
    if ((i >> j) & 1):
      score = score + np.array(a[j])
      now_p+=c[j]
  if np.count_nonzero(score < x) == 0 and price > now_p:
    price = now_p

if price < sum(c) +1:
  print(price)
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np


N, M, X = map(int, input().split())
books = np.array([list(map(int, input().split())) for i in range(N)])
minsum = N * 10**5
count = 0
check_array = []
success_array = []
for x in range(1, N + 1, 1):
    combi_list = list(itertools.combinations(range(N), x))
    for y in combi_list:
        sum_array = [0] * (M + 1)
        for z in y:
            sum_array = sum_array + books[z]
        beyond_check = True
        for zz in range(len(sum_array) - 1):
            if sum_array[zz + 1] < X:
                beyond_check = False
                break
        if beyond_check:
            success_array.append(sum_array[0])

    lenlist = len(combi_list)
    count += lenlist
if len(success_array) > 0:
    print(min(success_array))
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, XX = (int(i) for i in input().split())  

C = []
X = []
for _ in range(N):
    tmp = [int(i) for i in input().split()] 
    c = tmp[0]
    x = tmp[1:]
    C.append(c)
    X.append(x)

totalC = 10000000000000000
for ho in range((2 ** N)):
    tmp_c = 0
    tmp_x = [0] * (M)

    tmp = format(ho, '013b')[13-N:]
    for i in range(len(tmp)):
        if tmp[i] == "1":
            tmp_c += C[i]
            for ii in range(M):
                tmp_x[ii] += X[i][ii]


    flag = True
    for fu in tmp_x:
        if fu < XX:
            flag = False
    
    if flag & (tmp_c < totalC):
        totalC = tmp_c

if totalC == 10000000000000000:
    print("-1")
else:
    print(totalC)

Submission status: Accepted

Solution code:
from itertools import combinations

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

l=[list(map(int,input().split())) for _ in range(n)]
cost=float("inf")

for i in range(1,n+1):
    for l1 in combinations(l,i):
        score = [0]*m
        cost1=0

        for l2 in l1:
            cost1 += l2[0]
            for j in range(1,m+1):
                score[j-1] += l2[j]

        if min(score) >= x:
            cost = min(cost,cost1)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
san = list(tuple(map(int, input().split())) for _ in range(n))
dp = [float('inf')]*(1<<n)
ans = float('inf')
for i in range(1<<n):
    dai = 0
    ri = [0]*m
    for j in range(n):
        if i&(1<<j):
            dai += san[j][0]
            for k in range(1,m+1):
                ri[k-1] += san[j][k]
    for r in range(m):
        flag = True
        if ri[r]<x:
            flag = False
            break
    if flag:
        ans = min(ans, dai)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,X = list(map(int, input().split()))
C = [0 for i in range(N)]
A = [[0 for j in range(M)] for j in range(N)]
for i in range(N):
    A_ = list(map(int, input().split()))
    C[i] = A_[0]
    for j in range(M):
      A[i][j] = A_[j+1]
      
def check(books):
    algos_point = [0]*M
    for i in books:
        for j in range(M):
            algos_point[j] = algos_point[j] + A[i][j]
    for j in range(M):
        if algos_point[j] < X:
            return False
    return True

def cost(books):
    val = 0
    for i in books:
        val = val + C[i]
    return val
  
combi = []
for i in range(1,N+1):
    combi += list(itertools.combinations(list(range(N)), i))

vals = []
for c in combi:
  if check(c):
    vals.append(cost(c))
        
if vals == []:
  print(-1)
else:
  print(min(vals))

Submission status: Accepted

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""

from collections import deque
from itertools import product
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def floor(a, b):
    """floor(a/b) 整数値を返す"""
    c = (a - a % b)/b
    return int(c)


def main():

    N, M, X = wi()
    A = []
    for _ in range(N):
        A.append(wi())
    ans = 10**20
    flag = False
    for t in product([0, 1], repeat=N):
        plus = [0] * (M+1)
        plus = np.array(plus)
        flag = False
        for i in range(len(t)):
            if t[i] == 0:
                continue
            else:
                plus += np.array(A[i])
                #print(plus[0])
        for j in range(1, M+1):
            if plus[j] < X:
                flag = True
                break
        if flag == False:
            ans = min(ans, plus[0])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ca=[]
ans=float('inf')
for _ in range(n):
    ca.append(list(map(int,input().split())))
for i in range(2**n):
    money=0
    check=[0]*(m)
    for j in range(n):
        if ((i>>j)&1):
            money+=ca[j][0]
            for k in range(m):
                check[k]+=ca[j][k+1]
    if all(check[p]>=x for p in range(m)):
        ans=min(ans,money)
if ans==float('inf'):
    print('-1')
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m,x = map(int, input().split(" "))
infolist = []
for i in range(n):
  infolist.append(list(map(int, input().split(" "))))
  
optionlist = list(itertools.product('AB', repeat=n))

moneylist = []
#各オプションにつき
for option in optionlist:
  knowledge = [0]*m
  money = 0
  #各本につき
  for i in range(n):
    if option[i]=="A":
      #各ナレッジにつき参考書から加点
      for k in range(m):
        knowledge[k] += infolist[i][k+1]
      money += infolist[i][0]
  #オプション評価
  if all([p >= x for p in knowledge]):
    moneylist.append(money)

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

Submission status: Accepted

Solution code:
import itertools

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

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

allbooks = [sum([j[i] for j in CA]) for i in range(M+1)]

#print(allbooks)
if min(allbooks[1:]) < X:
    print(-1)
else:
    kingaku = allbooks[0]
    yobun = [i-X for i in allbooks[1:]]

    maxkingaku = 0
    go = True
    for k in range(1, N):
        if go == False:
            break
        allicombi = itertools.combinations(CA, k)
        OKs = 0
        for combi in allicombi:
            goukei = [sum([j[i] for j in combi]) for i in range(M+1)]
            if min([y-x for x,y in zip(goukei[1:], yobun)])>=0:
                OKs +=1
                if goukei[0] > maxkingaku:
                    maxkingaku = goukei[0]

        if OKs == 0:
            go = False
    print(kingaku - maxkingaku)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int, input().split())
c_a = [list(map(int, input().split())) for _ in range(n)]
argo_und = []
ans = 12*(10**5)
for i in range(2 ** n):
    flag = 0
    sums = np.zeros(m+1)
    for j in range(n):
        if ((i >> j) & 1):
            sums = sums + np.array(c_a[j])
    for j in range(1,m+1):
        if sums[j] < x:
            flag = 1
    if flag == 0:
        ans = min(ans, sums[0])
if flag == 1:
    print(-1)
else:
    print(int(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 20:50:51 2020
"""

import sys
#import numpy as np
import itertools

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

ans = 10 ** 9
for i in range(1,N+1):
    for C in itertools.combinations(ca,i):
#        print(C)
        tmp = 0
        m = [0 for _ in range(M)]
        for c in C:
            tmp += c[0]
            for i in range(M):
                m[i] += c[1+i]
        flg = True
        for mm in m:
            if mm < X:
                flg = False
        
        if flg:
            ans = min(ans,tmp)

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

Submission status: Accepted

Solution code:
N, M, X = list(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:])
# print(C)
# print(A)

bestmoney = float("inf")
for i in range(2**N):
    U = []
    for j in range(M):
#         print(j, [(((1<<k)&i)!=0)*A[k][j] for k in range(N)])
        u = sum([(((1<<k)&i)!=0)*A[k][j] for k in range(N)])
        U.append(u)
    flag = True
    for j in range(M):
        if U[j] < X:
            flag = False
            
#     print(bin(i),U,flag)
    if flag:
        bestmoney = min(sum([(((1<<k)&i)!=0)*C[k] for k in range(N)]), bestmoney)

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

coin = []
for i in range(1, n+1):
  for v in itertools.combinations(books, i):
    comb = list(v)
    result = np.sum(comb, axis = 0)
    
    flag = True
    for j in range(1,m+1):
      if result[j] < x:
        flag = False
        break
    if flag:
      coin.append(result[0])

if len(coin) > 0:
  coin.sort(reverse=False)
  print(coin[0])
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools


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

def can_reach(M, CA, X):
    understandig_list = [0] * M
    for CAi in CA:
        for j in range(1, len(CAi)):
            understandig_list[j - 1] += CAi[j] 

    can = all([understandig >= X for understandig in understandig_list])

    return can


if not can_reach(M, CA, X):
    print('-1')
    exit(0)

min_amount = 10 ** 5 * 12 + 1
for i in range(1, N + 1):
    combinations = itertools.combinations(range(N), i)

    for combination in combinations:
        understanding_list = [0] * M
        amount = 0
        for i in combination:
            for j in range(1, len(CA[i])):
                understanding_list[j - 1] += CA[i][j]
            amount += CA[i][0]

        # print(understanding_list)
        is_reached = all([understanding >= X for understanding in understanding_list])
        if not is_reached: continue

        min_amount = min(amount, min_amount)

print(min_amount)

Submission status: Accepted

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

listA=[] #appendのために宣言が必要
for _ in range(n):
    listA.append(list(map(int,input().split())))

kanoucost = []
for i in range(2**n):
    ls = [0]*n
    for j in range(len(ls)):
        if (i >> j) & 1:
            ls[j] = 1
    ability = [0]*(m+1)
    for k in range(len(ls)):
        new = [n * ls[k] for n in listA[k]]
        ability = [x + y for (x, y) in zip(ability, new)]

    if min(ability[1:]) >= x:
        kanoucost.append(ability[0])

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

Submission status: Accepted

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

moneys = []
skips = []

for i in range(1, 2**n):
  b = [int(_) for _ in list(format(i, '0{}b'.format(n)))]
  
  sums = [0]*m
  skip = [0]*m
  money = 0
  
  for j in range(n):
    if b[j] == 1:
      money += a[j][0]
      for k in range(m):
        sums[k] += a[j][k+1]
        if sums[k] >= x:
          skip[k] = 1
  if sum(skip) == m:
    moneys.append(money)
if len(moneys) > 0:
  print(min(moneys))
else:
  print(-1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
t = [0]*(m+1)
l = []
for i in range(n):
    l.append(list(map(int,input().split())))
    for j in range(m+1):
        t[j] += l[i][j]
p = 0
for i in range(1,m+1):
    if(t[i] < x):
        p = 1
        break
if(p == 1):
    print(-1)
else:
    c = t[0]
    for i in range(1,2**n):
        s = t.copy()
        z = str(bin(i)[2:])
        z = '0'*(n-len(z)) + z
        for j in range(n):
            if(z[j] == '0'):
                for k in range(m+1):
                    s[k] -= l[j][k]
        p = 0
        for j in range(1,m+1):
            if(s[j] < x):
                p = 1
                break
        if(p == 0):
            if(s[0] < c):
                c = s[0]
    print(c)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
mini = float('inf')
f=0

for i in range(2**n):
    v = [0]*m
    total = 0
    flag=0
    for j in range(n):  
        if ((i >> j) & 1):
            for k in range(m):
                v[k]+=a[j][k+1]
            total += a[j][0]
    for k in range(m):
        if v[k] < x:
            flag=1
    if flag == 0 and mini > total:
        mini = total
        f=1
        
if f == 0:
    print("-1")
else :
    print(int(mini))

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = map(int, input().split(" "))
c_min = np.inf
input_list = list(map(int, input().split(" ")))
c_list = np.array([input_list[0]])
a_list = np.array([input_list[1:]])
for _ in range(n - 1):
    input_list = list(map(int, input().split(" ")))
    c_list = np.append(c_list, input_list[0])
    a_list = np.vstack([a_list, input_list[1:]])

for i in range(1, 2 ** n):
    i_bin_str = str(bin(i))[2:]
    if len(i_bin_str) < n:
        i_bin_str = "0" * (n - len(i_bin_str)) + i_bin_str
    i_bin_list = np.array(list(map(int, list(f"{i_bin_str}"))))
    if len(a_list[i_bin_list > 0]) > 1:
        a_min = min(sum(a_list[i_bin_list > 0]))
    else:
        a_min = min(a_list[i_bin_list > 0][0])
    c_sum = sum(c_list[i_bin_list > 0])
    if a_min >= x and c_sum < c_min:
        c_min = c_sum

ans = -1 if np.isinf(c_min) else c_min
print(ans)