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 numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    res = 10 ** 9
    isFound = False

    for i in range(2**N):
        now = [0 for _ in range(M+1)]
        for j in range(N):
            if (i & (1<<j)):
                for k in range(M+1):
                    now[k] += CA[j][k]
        isOK = True
        for k in range(M):
            if now[k+1] < X:
                isOK = False
                break
        if isOK:
            res = min(res,now[0])
            isFound = True

    if not isFound:
        res = -1

    print(res)



main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
lis=[list(map(int,input().split())) for _ in range(n)]
ans=10**18
for i in range(2**n):
    l=[]
    rikai=[0]*m
    ok=True
    for j in range(n):
        if (i>>j)&1:
            l.append(j)
    cost=0
    for k in l:
        cost+=lis[k][0]
        for s in range(1,m+1):
            rikai[s-1]+=lis[k][s]
    for j in range(m):
        if rikai[j]<x:
            ok=False
    #print(l)
    if ok:
        ans=min(ans,cost)
if ans==10**18:
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

borders = np.ones(M+1) * X
borders[0] = 0
maxi = 2 ** N

init_cost = 10**8
cost = init_cost
for i in range(1,maxi):
    bits = [j for j in range(N) if (i >> j &1)]
    res = sum(books[bits])

    if np.all(np.where(res[1:] >= X, True, False)):
        cost = min(res[0],cost)

if cost == init_cost:
    print(-1)
else:
    print(cost)

Submission status: Accepted

Solution code:
from itertools import product

N,M,X=map(int,input().split())
C=[0]*N
A=[[0] for _ in range(N)]
for i in range(N):
  C[i],*A[i] = map(int,input().split())
  
s= product([1,0],repeat=N)
ans=float("inf")

for kumi in s:
  gou=True
  cost=0
  R=[0 for _ in range(M)]
  for i,n in enumerate(kumi):
    for j in range(M):  #アルゴリズム
      R[j] +=n*A[i][j]
    cost +=n*C[i]
  #print(R,cost)
  for pt in R:
    if pt<X:
      gou=False
  if gou:
    ans=min(ans,cost)
else:
  if ans!=float("inf"):
    print(ans)
  else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(N)]
ans = -1
cost = 10 ** 7
for i in range(2 ** N):
    bit = format(i, '0' + str(N) + 'b')
    A = [0] * M
    work_cost = 0
    counter = 0
    for b in bit:
        if b == "0":
            counter += 1
        else:
            work_cost += CA[counter][0]
            for i, ca in enumerate(CA[counter][1:]):
                A[i] += ca
            counter += 1
        # 理解度がX以上の参考書の数
    x = sum([1 for i in A if i >= X])
    if M == x:
        cost = min(cost, work_cost)
    # print(bit, work_cost, A)

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import numpy as np
from itertools import *
# from collections import *

# S = input()
# N = int(input())
# K, N = [int(x) for x in input().split()]

N, M, X = [int(x) for x in input().split()]

r = [0] * M
b = []

for n in range(N):
    b += [[int(x) for x in input().split()]]
C = []

for n in range(N):
    C += list(combinations(b, n+1))

minm = -1

for c in C:
    c = np.array(c)
    if min(np.sum(c[:, 1:M+1], axis=0)) >= X:
        if minm == -1 or np.sum(c[:, 0]) < minm:
            minm = np.sum(c[:, 0])

print(minm)

Submission status: Accepted

Solution code:
import itertools

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

mn = 10**10
for pat in itertools.product([0,1], repeat=N):
    cost = 0
    skills = [0]*M
    for i in range(N):
        cost += pat[i] * CA[i][0]
        for j in range(M):
            skills[j] += pat[i] * CA[i][j+1]
    ok = True
    for j in range(M):
        if skills[j] < X:
            ok = False
    if ok:
        mn = min(mn, cost)

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

Submission status: Accepted

Solution code:
# abc167_c.py
N, M, X = map(int,input().split())
C = []
A = []
for i in range(N):
    c,*a = map(int,input().split())
    C.append(c)
    A.append(a)

def calc_price(C,s):
    ans = 0
    for i,v in enumerate(s):
        if v==1:
            ans+=C[i]
    return ans


import itertools
status = [(0, 1) for _ in range(N)]
state = list(itertools.product(*status))
#print(state)
ans = 10**9+7
flg = -1
for s in state:
    price = 0
    gakuryoku = [0]*M
    for j,v in enumerate(s):
        if v == 1:
            price+=C[j]
            for k in range(M):
                gakuryoku[k] += A[j][k]
        if min(gakuryoku)>=X and ans > price:
            ans = price
            flg=0
if flg==-1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m,x = mi()

d = []
for i in range(n):
    d.append(li())

mincost = 10**10
for i in range(2**n):
    cost = 0
    tsd = [0] * m
    for j in range(n):
        if (i >> j)&1 == 1:
            cost += d[j][0]
            for k in range(m):
                tsd[k] += d[j][k+1]
    
    # print(bin(i),cost)
    for j in range(m):
        if tsd[j] < x:
            break
    else:
        mincost = min(cost,mincost)

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

Submission status: Accepted

Solution code:
#!python

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, M, X = iim()
    S = [tuple(iim()) for i in range(N)]

    M1 = M+1
    mx = float("inf")
    ans = mx
    for i in range(1, 2**N):

        sx = [0]*(M1)
        for j in range(N):
            if i & (1<<j) == 0:
                continue

            for k, x in enumerate(S[j]):
                sx[k] += x

        if all(si >= X for si in sx[1:]):
            ans = min(ans, sx[0])

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



if __name__ == "__main__":
    resolve()

Submission status: Accepted

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


def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

flag=0
cost=[]

import numpy as np

for i in range(2**N):
	price=0
	target=str(Base_10_to_n(i,2)).zfill(N)
	training=np.array([0]*M)
	for j in range(len(target)):
		if target[j]=="1":
			training=training+np.array(a_ls[j][1:])
			price+=a_ls[j][0]
	
	if sum(training>=np.array([X]*M))==M:
		flag=1
		cost+=[price]


if flag==1:
	print(str(min(cost)))
else:
	print("-1")

Submission status: Accepted

Solution code:

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

  books = []

  for _ in range(n):
    tpl = tuple(map(int, input().split()))
    books.append((tpl[0], tpl[1:]))

  dp = []

  for c, A in books:
    new_dp = [(c, A)]
    for total_cost, total_amount_list in dp:
      next_list = [A[i] + total_amount_list[i] for i in range(m)]
      new_dp.append((c + total_cost, next_list))

    dp.extend(new_dp)

  ans = tuple(filter(lambda tpl: min(tpl[1]) >= x, dp))
  if len(ans) == 0:
    print(-1)
  else:
    ans = sorted(ans, key=lambda tpl: tpl[0])[0]
    print(ans[0])


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Book:

    def __init__(self, info):
        self.cost = info[0]
        self.alg = info[1:]


class Solver:

    def __init__(self, books, x, m):
        self.books = books
        #print('self.books') # debug
        #print(self.books) # debug
        #print('self.books[0].cost') # debug
        #print(self.books[0].cost) # debug
        self.x = x
        self.m = m
        self.cost = 0
        self.skills = []
        self.ans = math.inf

    def run(self):
        for buy_book_bit in range(2 ** 12):
            self.shopping(buy_book_bit)
            if self.check():
                #print('self.cost') # debug
                #print(self.cost) # debug
                self.ans = min(self.ans, self.cost)
                #print('self.ans') # debug
                #print(self.ans) # debug
        return self.ans

    def check(self):
        for s in self.skills:
            if not (s >= self.x):
                return False
        return True

    def shopping(self, buy_book_bit):
        self.reset()
        for i, book in enumerate(self.books):
            #print('book') # debug
            #print(book) # debug
            key = 1 << i
            if key & buy_book_bit:
                self.buy(book)

    def reset(self):
        self.cost = 0
        self.skills = [0] * self.m

    def buy(self, book):
        self.cost += book.cost
        for i, a in enumerate(book.alg):
            self.skills[i] += a





if __name__ == '__main__':
    n, m, x = list(map(int, input().split()))
    books = []
    for i in range(n):
        info = list(map(int, input().split()))
        books.append(Book(info))
    ans = Solver(books, x, m).run()
    #print('ans') # debug
    if ans == math.inf:
        print(-1)
    else:
        print(ans)


    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(n)]
# print(info)
ans = float('inf')
for i in range(2**n):
    price = 0
    u = [0]*m
    for j in range(n):
        if (i>>j) & 1:
            price += info[j][0]
            for k in range(m):
                u[k] += info[j][k+1]
    ok = True
    # print(u)
    for l in range(m):
        if u[l] < x:
            ok = False
    if ok:
        ans = min(ans, price)

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

Submission status: Accepted

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

c = []
reference = []
for i in range(n):
    price, *a = map(int, input().split())
    c.append(price)
    reference.append(a)

understanding = [0] * m
price = 0
ans = sum(c) + 1

for i in range(2**n):
    understanding = [0] * m
    price = 0
    for j in range(n):
        if (i >> j) & 1:
            price += c[j]
            for k in range(m):
                understanding[k] += reference[j][k]
    
    flg = True
    for j in range(m):
        if understanding[j] < x:
            flg = False
            break
    
    if flg:
        ans = min(ans, price)
        
if sum(c) < ans:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ichizero=[]
for i in range(2**n):
    kari=[]
    for keta in reversed(range(n)):
        kari.append(i//(2**keta))
        i=i%(2**keta)
    ichizero.append(kari)

mincost=pow(10,7)

for now in ichizero:
    chokudai=[0]*m
    cost=0
    for j in range(n):
        if now[j]==1:
            cost+=kashiko[j][0]
            for k in range(m):
                chokudai[k]+=kashiko[j][k+1]

    if min(chokudai)>=x:
        if mincost>cost:
            mincost=cost

if mincost==pow(10,7):
    ans=-1
else:ans=mincost

print(ans)

Submission status: Accepted

Solution code:
# Contest No.: ABC167
# Problem No.: C
# Solver:      JEMINI
# Date:        20200510

import sys

def main():
    n, m, x = map(int, sys.stdin.readline().split())
    table = []

    for _ in range(n):
        table.append(list(map(int, sys.stdin.readline().split())))
    for i in range(1, m + 1):
        temp = 0
        for j in range(n):
            temp += table[j][i]
        if temp < x:
            print(-1)
            return
    ans = 0
    for i in range(n):
        ans += table[i][0]
    for i in range(1, 2 ** n):
        temp = i
        cnt = 0
        tempList = [0] * (m + 1)
        while temp > 0:
            if temp % 2:
                for j in range(m + 1):
                    tempList[j] += table[cnt][j]
            temp >>= 1
            cnt += 1
        flag = True
        for j in range(1, m + 1):
            if tempList[j] < x:
                flag = False
                break
        if flag:
            ans = min(ans, tempList[0])
    print(ans)    
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

n, m, x = map(int, input().split())
ca = np.array([list(map(int, input().split())) for _ in range(n)], dtype="i8")

ans = 10 ** 20
for bit in product([0, 1], repeat=n):
    tmp = np.zeros(m + 1)
    for i, j in enumerate(bit):
        if j == 1:
            tmp += ca[i]
    f = 0
    for i in tmp[1:]:
        if i < x:
            f = 1
    if f == 0:
        ans = min(ans, tmp[0])

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

Submission status: Accepted

Solution code:
from itertools import combinations

def appliquer(a, cb, n, m, x, c):
	cout = 0
	l = [0]*m
	# ~ print(l, a)
	# ~ print("c",c) 
	# ~ print("cb",cb)
	for i in cb:
		for j in range(m):
			# ~ print("a[i][j] = ",a[i][j])
			l[j]+=a[i][j]
		cout+=c[i]
	# ~ print(cb, cout, l,x)
	return cout if all(i>=x for i in l ) else -1

n,m,y = (int(i) for i in input().split())

c = [0]*n
a = []
for i in range(n):
	t = [int(i) for i in input().split()]
	c[i] = t[0]
	a.append(t[1:])
	
rng = [i for i in range(n)]

ans = 100000000

for x in range (1,n+1):
	comb = list(combinations(rng, x))
	for cb in comb:
		cout = appliquer(a, cb, n, m, y, c)
		if cout>=0:
			ans = min(ans, cout)
			# ~ print(cb,"->",cout)
			
print(ans if ans != 100000000 else -1)

Submission status: Accepted

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


import itertools
INF = 10 ** 10
ans = INF
for bi in itertools.product([0, 1], repeat=n):
    xx = [0] * m
    cc = 0
    for i, j in enumerate(bi):
        if j == 1:
            for k in range(m):
                xx[k] += ca[i][k+1]
            cc += ca[i][0]
    allok = True
    for i in range(m):
        if xx[i] < x:
            allok = False
    if allok:
        ans = min(ans, cc)
if ans == INF:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

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

cnt = float("inf")
for i in range(2**N):
  bs = "0" + format(i,"0{}b".format(N))
  ansl = [0 for _ in range(M+1)]
  for j in range(1,N+1):
    if bs[j] == "1":
      for k in range(M+1):
        ansl[k] += l[j][k]
  #判定
  for j in range(1,M+1):
    if ansl[j] < X:
      break
    if j == M:
      cnt = min(cnt,ansl[0])
if cnt == float("inf"):
  cnt = -1      
print(cnt)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''

    N, M, X = [int(item) for item in input().split()]
    data = [[int(item) for item in input().split()] for _ in range(N)]

    cost = 10**9

    for i in range(2**N):
        temp_point = [0 for _ in range(M)]
        temp_cost = 0
        for j in range(N):
            if ((i >> j) & 1):
                for k, v in enumerate(data[j][1:]):
                    temp_point[k] += v
                temp_cost += data[j][0]

        is_flag = True
        for temp_p in temp_point:
            if temp_p < X:
                is_flag = False
                break
        
        if is_flag:
            cost = min(cost, temp_cost)

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N,M,X=map(int, input().split())
C=[]
A=[]
for i in range(N):
  d=list(map(int, input().split()))
  c1=d[0]
  c2=d[1:]
  C.append(c1)
  A.append(c2)
R=[0]*M
for i in range(N):
  for j in range(M):
    R[j]+=A[i][j]
    
if min(R)<X:
  print(-1)
  exit()

import itertools
D=list(itertools.product([0,1], repeat=N))
ans=(10**5)*12
for i in range(len(D)):
  L=[0]*M
  cnt=0
  for j in range(N):
    cnt+=D[i][j]*C[j]
    for k in range(M):
      L[k]+=D[i][j]*A[j][k]
  if min(L)>=X:
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import math

N,M,X = map(int, input().split())
S = set([tuple([0]*(M+1))])

for _ in range(N):
    CA = list(map(int, input().split()))

    S2 = set()
    for s in S:
        S2.add(tuple([s[i] + CA[i] for i in range(M+1)]))

    S |= S2

minC = math.inf
for s in S:
    for i in range(M):
        if s[i+1] < X:
            break
    else:
        minC = min(minC, s[0])

if minC == math.inf:
    print(-1)
else:
    print(minC)

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(N)]
res = float('inf')

def dfs(A):
    global res
    if len(A) == N:
        tmp = np.array([0]*M)
        tmp_c = 0
        for i, a in enumerate(A):
            if a == 1:
                tmp += np.array(books[i][1:])
                tmp_c += books[i][0]

        if np.all(tmp >= X):
            if tmp_c < res:
                res = tmp_c

        return

    dfs(A + [0])
    dfs(A + [1])


dfs([])
if res == float('inf'):
    res = -1
print(res)

Submission status: Accepted

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

def input_one_number():
    return int(input())

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

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


N,M,X =  input_multiple_number()

listC = [0]*N
tableA = [[0]*M for i in range(N)]

for i in range(N):
	iii = input_multiple_number_as_list()
	listC[i] = iii[0]
	for j in range(M):
		tableA[i][j] = iii[j+1]
INF = 10000000000
ans = INF

import itertools as it
for i in it.product(range(2), repeat=N):
	isOK = True
	price = 0
	listM = [0]*M
	for j in range(N):
		if i[j] == 1:
			for qqq in range(M):
				listM[qqq] += tableA[j][qqq]
			price += listC[j]
	for skils in range(M):
		isOK = (listM[skils] >= X) and isOK

	if isOK:
		ans = min(price,ans)

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

Submission status: Accepted

Solution code:
import numpy as np

N,M,X = map(int,input().split())
book = [list(map(int,input().split())) for i in range(N)]
npbook = np.array(book)
flag = -1
minsum = 1000000000

for i in range(2**N):
    sumyenskill = np.zeros(M+1)
    for j in range(N):
        if (i>>j)&1 ==1:
            sumyenskill += book[j]

    if min(sumyenskill[1:M+2])>=X:
        flag = 1
        if sumyenskill[0]<minsum:
            minsum = sumyenskill[0]

if flag ==1:
    print(int(minsum))
else:
    print(-1)

Submission status: Accepted

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

C = []
A = [ [] for _ in range(N)]
for i in range(N):
    A[i] = [int(x) for x in input().split()]

cost = 10**5 * N
f = False
for i in range(2**N):
    BAG = [0]*(1+M)
    for j in range(N):
        if bin(i>>j)[-1] == '1':
            for k in range(1+M):
                BAG[k] += A[j][k]

    for k in range(1,1+M):
        if BAG[k] < X:
            break
    else:
        f = True
        cost = min(cost,BAG[0])

if f:
    print(cost)
else:
    print(-1)

Submission status: Accepted

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

ans = float("inf")

for i in range(2**N):
    l = [0 for _ in range(M)]
    c = 0
    for j in range(N):
        if i >> j & 1:
            l = [x + y for (x, y) in zip(ca[j][1:], l)]
            c += ca[j][0]

    l_bool = [a >= X for a in l]
    if all(l_bool):
        ans = min(ans, c)

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

else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
data = []
a = [0]*n
ans = float('inf')

for i in range(n):
    d = list(map(int,input().split()))
    data.append(d)

def bfs(arrs):
    if len(arrs) == n:
        global ans
        a = [0]*m
        c = 0
        for i in range(n):
            if arrs[i]==1:  
                C = data[i][0]
                A = data[i][1:]
                c += C
                for j in range(m):
                    a[j] += A[j]
        for i in a:
            if i<x:return
        ans = min(ans,c)
    else:
        bfs(arrs + [0])
        bfs(arrs + [1])

bfs([])
if ans == float('inf'):ans=-1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

inputs = []
for _ in range(n):
    input_ = map(int, input().split(" "))
    inputs.append(input_)


first = True
min_cost = None
for ui, uses in enumerate(list(itertools.product(*(tuple([[True, False]] * n))))):
    cur_cost = 0
    a_list = [0 for _ in range(m)]
    for i in range(n):
        if uses[i]:
            cur_input = inputs[i]
            c = cur_input[0]
            cur_cost += c
            for ai, a in enumerate(cur_input[1:]):
                a_list[ai] += a


    if first or min_cost > cur_cost:
        count = 0
        ok = True
        for ai, a in enumerate(a_list):
            if a < x:
                ok = False
                break

        if ok:
            first = False
            min_cost = cur_cost

if min_cost is None:
    min_cost = -1
print(min_cost)

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    n, m, x = map(int, input().split())
    in_lis = []
    for _ in range(n):
        in_lis.append(list(map(int, input().split())))
    
    #print(in_lis)
    ans = 10 ** 10
    for i in range(1, 2 ** n):
        tmp = 0
        bag = []
        for j in range(n):
            if ((i >> j)& 1):
                bag.append(in_lis[j])
        a = np.array(bag)
        #print( np.sum(a, axis = 0))
        sum_retsu = np.sum(a, axis = 0)
        cnt = 0
        #print(sum_retsu)
        for k in range(1, m+1):
            if sum_retsu[k] >= x:
                cnt += 1
        if cnt == m:
            tmp = sum_retsu[0]
            ans = min(ans, tmp)
    if ans ==  10 ** 10:
        ans = -1
    print(ans)

    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M,X = list(map(int, input().split()))
C = []
A = []
for i in range(N):
  temp = list(map(int, input().split()))
  C.append(temp[0])
  A.append(temp[1:])
moneylist = []
for i in range(2**N):
  Xtemp = []
  moneytemp = 0
  for j in range(M):
    Xtemp.append(0)
  for j in range(N):
    if((i >> j) & 1): #iを右にjビットシフトして、その最下位ビットが1かどうか判定
      for k in range(M):
        Xtemp[k] += A[j][k]
      moneytemp += C[j]
  flag = 0
  for j in range(M):
    if(Xtemp[j] < X):
      flag = 1
      break
  if(flag==0):
    moneylist.append(moneytemp)
  
if(len(moneylist)==0):
  print(-1)
else:
  print(min(moneylist))

Submission status: Accepted

Solution code:
N, M, X = list(map(int, input().split()))
C_A = [list(map(int, input().split())) for _ in range(N)]
slv_cost = 0
A = [0]*M
for i in range(N):
    slv_cost += C_A[i][0]
    for j in range(M):
        A[j] += C_A[i][j+1] 

for i in range(M):
    if X > A[i]:
        print(-1)
        exit()

for i in range(1, 2**N):
    st = bin(i)[2:][::-1]
    tmp_A = [0]*M
    tmp_cost = 0
    for j in range(len(st)):
        if st[j] == "1":
            tmp_cost += C_A[j][0]
            for l in range(M):
                tmp_A[l] += C_A[j][l+1]
    ok = True
    for j in range(M):
        if X > tmp_A[j]:
            ok = False
    if ok == True:
        slv_cost = min(slv_cost, tmp_cost)
print(slv_cost)

Submission status: Accepted

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

ck = 0
ARR = []
for i in range(2 ** N):
  ans= 0
  bag = [0 for j in range(M)]
  for j in range(N):  # このループが一番のポイント
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      a = arr[j]
      ans += a[0]
      for k in range(M):
        bag[k] += a[k+1]
  if min(bag) >= X:
    ck = 1
    ARR.append(ans)

if ck == 0:
  print(-1)
else:
  print(min(ARR))

Submission status: Accepted

Solution code:
INF = 99999999999

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

for _ in range(n):
    a_list = list(map(int, input().split())) 
    c_l.append(a_list[0])
    a_l.append(a_list[1:])

min_c = INF
for i in range(2 ** n):
    bag_c = []
    bag_a = []
    for j in range(n):
        if ((i >> j) & 1):  
            bag_c.append(c_l[j])  
            bag_a.append(a_l[j])
        l = len(bag_a)
        c_sum = 0
        s_sum = [0]*m
        for ii in range(l):
            c_sum += bag_c[ii]
            for mm in range(m):
                s_sum[mm] += bag_a[ii][mm]
        if min(s_sum) >= x and c_sum < min_c:
            min_c = c_sum
if min_c == INF:
    print(-1)
else:   
    print(min_c)

Submission status: Accepted

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

ans = 10**9

for i in range(2**n):
    ls = [0] * m
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            ls = [l + a for l, a in zip(ls, CA[j][1:])]
            tmp += CA[j][0]
    if all(i >= x for i in ls):
        ans = min(ans, tmp)
print(ans if ans != 10**9 else -1)

Submission status: Accepted

Solution code:
def main():
    n,m,x = map(int,input().split())
    a = [list(map(int,input().split())) for i in range(n)]
    res = 10**18
    from itertools import product
    for i in product(range(2), repeat=n):
        tmp = 0
        rikai = [0]*m
        okflg = False
        for j in range(n):
            if i[j] == 1:
                tmp += a[j][0]
                okflg = True
                for k in range(1,m+1):
                    rikai[k-1] += a[j][k]
                    if rikai[k-1] < x:
                        okflg = False
                if okflg == True:
                    break
        if okflg == True:
            res = min(tmp,res)
    if res == 10**18:
        print(-1)
    else:
        print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def main():
    N, M, X = map(int, input().split())
    C_A_list = [[int(_) for _ in input().split()] for i in range(N)]

    bit = 1 << N
    INF = float('inf')
    min_price = INF
    for i_bit in range(bit):
        price = 0
        understand_list = [0] * M
        for j_N in range(N):
            if i_bit & (1 << j_N) == 0:
                continue

            price += C_A_list[j_N][0]
            for i, i_A in enumerate(C_A_list[j_N][1:]):
                understand_list[i] += i_A

        for i_understand in understand_list:
            if i_understand < X:
                break
        else:
            min_price = min(min_price, price)

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

    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Accepted

Solution code:
def study(A,C,m,n,b,x):
    B = [0 for _ in range(m)]
    cost = 0
    for i in range(n):
        if b[i] == "1":
            for j in range(m):
                B[j] += A[i][j]
            cost += C[i]
    if min(B) >= x:
        return (True,cost)
    else:
        return (False,-1)

def pad(b,n):
    if len(b) < n:
        b = "0"*(n-len(b)) + b
    return b

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

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

    INF = 12*10**5+1
    ans = INF
    for i in range(2**N):
        b = pad(bin(i)[2:],N)
        st = study(A,C,M,N,b,X)
        if st[0]:
            cost = st[1]
            ans = min(ans,cost)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

text = []
min_money = 100000000
for i in range(N):
  ca = list(map(int,input().split()))
  text.append((ca[0],ca[1:]))
for i in range(2 ** N):
    und = [0]*M
    money = 0
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
          und = [x + y for (x, y) in zip(text[j][1], und)]
          money += text[j][0]
    if all([i >= X for i in und]) and money < min_money:
      min_money = money

if min_money == 100000000:
  min_money = -1
print(min_money)

Submission status: Accepted

Solution code:
mod=1000000007
n,m,x=map(int,input().split())
w=[]
for i in range(n):
    w.append([int(i) for i in input().split()])
ans=mod
for i in range(2**n):
    d=0
    chk=[0]*m
    for j in range(n):
        if (i>>j&1):
            d+=w[j][0]
            for k in range(m):
                chk[k]+=w[j][k+1]

    if min(chk)>=x:
        ans=min(ans,d)
#print(ans)
print(ans if ans!=mod else -1)

Submission status: Accepted

Solution code:
# Problem C - Skill Up

# input
N, M, X = map(int, input().split())
book_list = []
for i in range(N):
    book = list(map(int, input().split()))
    book_list.append(book)

# initialization
price = float('INF')
is_ok = False

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

for p in pattern:
    tmp_sum = [0]*(M+1)
    is_finish = True
    for i in range(N):
        if p[i]==1:
            for j in range(M+1):
                tmp_sum[j] += book_list[i][j]
    # check
    for i in range(1, M+1):
        if not tmp_sum[i]>=X:
            is_finish = False
            break

    if is_finish:
        is_ok = True
        price = min(price, tmp_sum[0])

# output
if is_ok:
    print(price)
else:
    print(-1)