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 *

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

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




res = []

for a in product((0,1), repeat=N):
    P = [0] * M
    cost = 0
    for i in range(N):
        if a[i]:
            cost += C[i]
            for j in range(M):
                P[j] += A[i][j]
    for j in range(M):
        if P[j] < X:
            break
        if j == M-1:
            res.append(cost)

if not res:
    print(-1)
else:
    print(min(res))

Submission status: Accepted

Solution code:
# C - Skill Up
N,M,X = map(int,input().split())
A = [[] for _ in range(N)]
for i in range(N):
    A[i] = list(map(int,input().split()))
ans = 10**9
for x in range(1,1<<N):
    C = [0]*M
    cost = 0
    for i in range(N):
        if x>>i&1==1:
            for j in range(M):
                C[j] += A[i][j+1]
            cost += A[i][0]
    if all([c>=X for c in C]):
        ans = min(ans,cost)
if ans==10**9:
    ans = -1
print(ans)

Submission status: Accepted

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

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

money = []
for i in range(n):
    a = list(map(int, input().split()))
    money.append(a[0])
    for j in range(m):
        li[j].append(a[j+1])

ans = sum(money) + 1
first = ans

for hh in range(1 << n):
    cnt = 0
    for i in range(m):
        s = 0
        for h in range(n):
            if (hh >> h)%2 == 1:
                continue
            s += li[i][h]
        if s >= x:
            cnt += 1
    if cnt == m:
        an = 0
        for h in range(n):
            if (hh >> h)%2 == 1:
                continue
            an += money[h]
        ans = min(ans, an)

if ans == first:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:

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

c = []

ans = 10**9

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

for i in range(2**n):
    t = []
    r = [0]*m
    cost = 0
    for s in range(n):
        if i >> s & 1:
            t.append(s)
    
    for tx in t:
        cost += c[tx][0]
        for x in range(m):
            r[x] += c[tx][x+1]

    if min(r)>xm-1:
        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())
A = []
cost = []
for i in range(N):
    a = list(map(int,input().split()))
    A.append(a[1:])
    cost.append(a[0])
ans = float('inf')
for i in range(2**N):
    I = bin(i)[2:]
    I = I.zfill(N)
    tmp = [0]*M
    buy = 0
    for j in range(len(I)):
        if I[j]=='1':
            for k in range(len(A[j])):
                tmp[k] += A[j][k]
            buy += cost[j]
    if all(tmp[i]>=X for i in range(len(tmp))):
        ans = min(ans,buy)
ans = -1 if ans ==float('inf') else ans
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

INF = 10**8
N,M,X=map(int, input().split())
C = []
A = [[0 for i in range(M)] for j in range(N)]

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

C, A = map(np.array, [C,A]) 
min_ = INF
for i in range(1,N+1):
  for c in combinations(range(N),i):
    if (A[c,:].sum(0) >= X).sum() == M:
      if C[list(c)].sum() < min_:
        min_ = C[list(c)].sum()

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

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
ref = []
c = []
for i in range(n):
  ref.append(list(map(int, input().split())))
  c.append(ref[i].pop(0))
ans = sum(c)
ok = False
for i in range(1<<n):
  cost = 0
  skill = [0]*m
  for r,j in enumerate(ref):
    if (i>>r)&1 == 1:
      cost += c[r]
      for k in range(m):
        skill[k] += j[k]
  if min(skill)>=x:
    ok = True
    if cost < ans:
      ans = cost
if ok:
  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)]
#print(ca)
ans=10**18
for BIT in range(1<<n):
    l=[0]*m
    tmp=0
    t=0
    b="0"*(n-len(bin(BIT)[2:]))+bin(BIT)[2:]
    book=[]#購入する本のリスト
    for i in range(n):
        if b[-i-1]=="1":
            book.append(i)
    #print(b,book)
    for j in range(n):
        if j in book:
            for k in range(1,m+1):
                l[k-1]+=ca[j][k]
            tmp+=ca[j][0]
    #print(tmp,l,b,book)
    for z in range(m):#x以上かチェック
        if l[z]<x:
            t=1
            continue
    if t==1:
        continue
    if ans>tmp:
        ans=tmp
    #print(ans,tmp,l)
if ans==10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

N, M, X = map(int, input().split())
C = list()
A = [[] for _ in range(N)]
for i in range(N):
  arg = list(map(int, input().split()))
  C.append(arg[0])
  A[i] = arg[1:]
h = []
# 参考書を選択するパターンは2のN乗通り
for i in range(2**N):
  cost = 0
  rikaido = [0] * (M)
  sankosyo = list()
  for j in range(N):
    if (i >> j) & 1:
      # 参考書jを選択
      sankosyo.append(j)
      cost += C[j]
  for k in sankosyo:
    for l in range(M):
      rikaido[l] += A[k][l]
  if min(rikaido) >=  X:
    heapq.heappush(h, cost)
if len(h) > 0:
  print(h[0])
else:
  print(-1)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(1000000)

def dfs(cost, i, A):
    if i == n-1:
        global ans
        if cost < ans and all([ai>=x for ai in A]):
            ans = cost
        return
    i += 1
    dfs(cost, i, A)
    dfs(cost+c[i], i, A+a[i])

    

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    c, a = [None]*n, np.array([None]*n)
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    ans = 10**10
    dfs(0, -1, np.array([0]*m))
    if ans == 10**10:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

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

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

for i in range(N):
    tmp = [int(x) for x in input().split()]
    C[i] = tmp[0]
    A[i] = tmp[1:]
min = sum(C) + 1

for i in range(2**N):
    cost = 0
    ANS = [0]*M

    for j in range(N):
        if((i>>j) & 1):
            cost += C[j]
            for k in range(M):
                ANS[k] += A[j][k]

    # print("cost=",cost,"ANS=",ANS)
    ans = 1
    for j in ANS:
        if(j < X):
            ans = 0


    if(ans and cost < min):
        min = cost

# print(min)
if(min == sum(C)+1):
    print(-1)
else:
    print(min)

Submission status: Accepted

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

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

ans = 10**30
for i in range(2**N):
  cost = 0
  gain = [0 for _ in range(M+1)]
  j = i
  keta = 0
  while j > 0:
    if j & 1:
      cost += A[keta][0]
      for l in range(1,M+1):
        gain[l] += A[keta][l]
        #print(i,j,l,gain)
    j = j >> 1
    keta += 1
    
  result = True
  for l in range(1,M+1):
    if gain[l] < X:
      result = False
      break
    
  if result == True:
    ans = min(ans, cost)
      
print(ans if ans < 10**30 else -1)

Submission status: Accepted

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

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

for i in range(2**n):
    total = 0
    r = [0]*m
    flag = True
    for j in range(n):
        if (i>>j) & 1:
            total += C[j] 
            for k in range(m):
                r[k] += A[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)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N, M, X = [int(_) for _ in input().split()]
CA = np.array([[int(_) for _ in input().split()] for _ in range(N)], dtype=int)
ans = 10**10
for bs in itertools.product(range(2), repeat=N):
    s = np.zeros(M + 1, dtype=int)
    for i, b in enumerate(bs):
        if b:
            s += CA[i]
    if np.all(s[1:] >= X):
        ans = min(ans, s[0])
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from math import inf
n, m, x = map(int, input().split())
ca = list()
for _ in range(n):
    ca.append(list(map(int, input().split())))

money = inf
tmp = 1
for i in range(n):
    tmp += 2**i
for i in range(tmp):
    B = str(format(i, str(n).zfill(n)+'b'))
    j = 0
    cnt = 0
    a = [0]*m
    for ch in B:
        if ch == '1':
            cnt += ca[j][0]
            for k in range(1, m+1):
                a[k-1] += ca[j][k]
        j += 1
    for ch in a:
        if ch < x:
            break
    else:
        money = min(cnt, money)
print(-1 if money == inf else money)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
e=10**8
for i in range(n):
    b=list(map(int,input().split()))
    a.append(b)
for i in range(2**n):
    c=[0]*(m+1)
    s=0
    for j in range(n):
        if i>=2**(n-j-1):
            i-=2**(n-j-1)
            c=[x+y for (x,y) in zip(a[j],c)]
    for j in range(m):
        if c[1+j]<x:
            s+=1
    if s==0 and e>c[0]:
        e=c[0]
if e==100000000:
    print(-1)
else:
    print(e)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N, M, X = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(N)]
ans = 10 ** 10
for i in range(2 ** N):
    p = [0] * M
    sum = 0
    for j in range(N):
        if ((i >> j) & 1):
            sum += li[j][0]
            for k in range(M):
                p[k] += li[j][k + 1]
        if all(x >= X for x in p):
            ans = min(sum, ans)

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

Submission status: Accepted

Solution code:
import math

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

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

ans = math.inf

for i in range(2**N):
    a = [0]*M
    c = 0

    flag = True
    
    for j in range(N):
        if ((i >> j) & 1):
            a = list(map(sum, zip(a, A[j-1])))
            c += C[j-1]

    for x in a:
        if x < X:
            flag = False
            break
    
    if flag:
        ans = min(ans, c)

if ans == math.inf:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:

import itertools

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

ans = -1
for cart in itertools.product([True, False], repeat=n):
    price = 0
    score = [0] * m
    for ni in range(n):
        if cart[ni]:
            price += c[ni]
            for mi in range(m):
                score[mi] += a[ni][mi]
    score_check = True
    for mi in range(m):
        if score[mi] < x:
            score_check = False
            break
    if score_check:
        if ans == -1:
            ans = price
        else:
            ans = min(ans, price)

print(ans)

Submission status: Accepted

Solution code:
def mi(): return map(int,input().split())
def lmi(): return list(map(int,input().split()))
def ii(): return int(input())
def isp(): return input().split()

import sys
import numpy as np

sys.setrecursionlimit(10**8)
n,m,x=mi()
list_ans=[]
for i in range(n):
  c_=lmi()
  list_ans.append(c_)

ans=float('inf')

def dfs(i,suma,count):
  global ans
  if i==n:
    
    if np.all(count>=x):
      ans=min(ans,suma)
      return ans

  else:
    dfs(i+1,suma,count)
    dfs(i+1,suma+list_ans[i][0],count+np.array(list_ans[i][1:]))

dfs(0,0,np.array([0]*m))
if ans==float('inf'):
  print(-1)
  exit()
  
else:
  print(ans)

Submission status: Accepted

Solution code:
import math
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
  l = list(map(int, input().split()))
  C.append(l[0])
  A.append(l[1:])
  
ans = math.inf
for i in range(2**N):
  a = [0]*M
  c = 0
  flag = True
  for j in range(N):
    if ((i >> j) & 1):
      a = list(map(sum, zip(a, A[j-1])))
      c += C[j-1]
  for x in a:
    if x < X:
      flag = False
      break
  if flag:
    ans = min(ans, c)
    
if ans == math.inf:
  ans = -1
print(ans)

Submission status: Accepted

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

for i in range(2**n):#全探索ループ
  bin(i)
  d=[0 for _ in range(m+1)]
  
  for j in range(n):#それぞれの本
    if ((i >> j) & 1):#フラグ立ってると足してく
      for k in range(m+1):
        d[k]+=c[j][k]
        
  for j in range(m):
    if d[j+1] <x:
      break
  else:
    if sm>d[0] or sm==-1:
      sm=d[0]
      
print(sm)

Submission status: Accepted

Solution code:
import sys
import numpy as np
def Ii():return int(sys.stdin.buffer.read())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))
  
n,m,x = Mi()
a = []
b=[0]*m
b = np.array(b)
for i in range(n):
  a.append(Li())
  
ans = 10**7
def DFS(cost,start,skill):
  global ans
  if min(skill) >= x:
    ans = min(ans,cost)
    return ans
  for i in range(start,n):
    DFS(cost+a[i][0],i+1,skill+np.array(a[i][1:]))
  return ans

a = DFS(0,0,b)
if a == 10**7:
  a = -1
print(a)

Submission status: Accepted

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

(n, m, x), cost = map(int, input().split()), sys.maxsize
s = [list(map(int, input().split())) for i in range(n)]
for i in range(1, 1 << n):
    k, y = [0 for i in range(m)], 0
    for j in range(n):
        if (i >> j) & 1:
            for ii in range(1, m + 1): k[ii-1] += s[j][ii]
            y += s[j][0]
    if all([k[j] >= x for j in range(m)]): cost = min(cost, y)
print(-1 if cost == sys.maxsize else cost)

Submission status: Accepted

Solution code:
#create date: 2020-07-03 10:17

import sys
stdin = sys.stdin
from itertools import product
import numpy as np

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m, x = na()
    c, a = list(), list()
    for i in range(n):
        ci, *ai = na()
        c.append(ci)
        a.append(ai)
    a = np.array(a)
    buy_book = product([0,1], repeat=n)
    ans = 10**10
    f = False
    for book_list in buy_book:
        cost = 0
        b = [0] * m
        for book, ci, ai in zip(book_list, c, a):
            if book==1:
                cost += ci
                b += ai
        if np.min(b) >= x:
            f = True
            ans = min(ans, cost)
    print(ans if f else -1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#cited from c-yan
N, M, X = map(int, input().split())

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

result = -1
for i in range(1 << N):
    t = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Submission status: Accepted

Solution code:
Max = 100000000
N, M, X = map(int, input().split())
A = []
for j in range(N):
	A.append(list(map(int, input().split())))

R = 2**N
ans = Max
for i in range(R):
	cost = 0
	check = M*[0]
	#print(check)
	for j in range(N):
		if (i>>j)&1:
			cost += A[j][0]
			for k in range(M):
				check[k] += A[j][k+1]

	judge = 1
	for j in range(M):
		if  check[j] < X:
			judge = 0
			break
	if judge==1:
		ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
ca_list = [list(map(int, input().split())) for _ in range(N)]
c = [ca_list[i][0] for i in range(N)]
a = [ca_list[i][1:] for i in range(N)]

a = np.array(a)
cost = 1000000000000000000

for i in range(1, 2 ** N):
    skill = np.zeros((1, M))
    money = 0
    for j in range(N):
        if (i >> j) & 1:
            skill += a[j]
            money += c[j]

    if np.all(skill >= X):
        cost = min(cost, money)

if cost == 1000000000000000000:
    cost = -1

print(cost)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n, m, x = map(int, input().split())
a = np.dot([i for i in itertools.product([0, 1], repeat = n)],
           [list(map(int, input().split())) for _ in range(n)])
b = np.prod(a[:, 1:(m + 1)] >= x, axis = 1, dtype = bool)
print(min(a[:, 0][b]) if b.sum() else '-1')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

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

    ans = 10**10

    for i in range(2 ** n):
        skill = [0]*m
        cost = 0
        for j in range(n):  # このループが一番のポイント
            if ((i >> j) & 1):
                cost += l[j][0]
                for k in range(m):
                    skill[k] += l[j][k+1]
        if all(skill[i] >= x for i in range(m)):
            ans = min(ans, cost)

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


resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
from itertools import combinations
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M, X = map(int, input().split())
    CA = [[] for _ in range(N)]
    for n in range(N):
        CA[n] = list(map(int, input().split()))
 
    COSTS = []
    for n in range(N):
        for c in combinations(CA, n+1):
            SUM = [0 for _ in range(M)]
            COST = 0
            for ca in c:
                COST += ca[0]
                for m in range(M):
                    SUM[m] += ca[m+1]
            if all(list(map(lambda x: x >= X, SUM))):
                COSTS.append(COST)
    if COSTS:
        print(min(COSTS))
        return
    print(-1)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c=[]
for i in range(n):
  a=[int(i) for i in input().split()]
  c.append(a)
import numpy as np
c=np.array(c)
ans=float('inf')
for i in range(1,2**n):
  p=[0]*m
  cost=0
  for j in range(n):
    if(i>>j)&1==1:
      cost+=c[j][0]
      p+=c[j][1:]
    if min(p)>=x:
      ans=min(ans,cost)
       
if ans==float('inf'):
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
c = []
for i in range(n):
  a = [int(i) for i in input().split()]
  c.append(a)
  
c = np.array(c)
ans = float('inf')
for i in range(1,2**n):
  chk = [0]*m
  cost = 0
  for j in range(n):
    if (i>>j)&1 == 1:
      cost += c[j][0]
      chk += c[j][1:]
  if min(chk) >= x:
    ans = min(ans,cost)
  
if ans == float('inf'):
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
#入力部
n,m,x = map(int,input().split())
a = []
c = []
for s in range(n):
	c_tmp,*a_tmp = list(map(int,input().split()))
	c.append(c_tmp)
	a.append(a_tmp)
#ビット全探索処理
c_ans = []
for i in range(2**n):
	ans_box = [0]*m
	c_box = 0
	for j in range(n):
		if(i>>j)&1 == 1:
			for p in range(m):
				ans_box[p] += a[j][p]
			c_box += c[j]
	if min(ans_box) >= x:
		c_ans.append(c_box)
#出力部
print(min(c_ans) if len(c_ans)>0 else -1)

Submission status: Accepted

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

for i in range(1,2**n) :
    a = format(i,"b")
    a = a.zfill(n)
    ans = [0]*(m+1)
    for j in range(n) :
        if a[j] == "1" :
            ans = list(map(lambda s,t: s+t, ans , ca[j]))
    l = 0
    for k in range(1,m+1) :
        if ans[k] >= x :
            l += 1
    if l == m :
        money.append(ans[0])

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

Submission status: Accepted

Solution code:
import numpy as np
N, M, X = map(int, input().split())
A = []
C = []
for _ in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)
A = np.array(A,dtype=int)
ans = 10 ** 7
for bit in range(2 ** N):
    B = np.zeros(M, dtype=int)
    cost = 0
    for i in range(N):
        if bit & (1<<i):
            B += A[i]
            cost += C[i]
    if np.all(B >= X):
        ans = min(ans, cost)
print(ans if ans < 10**7 else -1)

Submission status: Accepted

Solution code:
from sys import stdin
a = stdin.readlines()

n = int(a[0].split()[0])
m = int(a[0].split()[1])
x = int(a[0].split()[2])

l = []
for i in range(n):
    tmp = []
    for j in range(m+1):
        tmp.append(int(a[i+1].split()[j]))
    l.append(tmp)

ans = []
for i in range(2**n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(l[j])
    s = [0]*(m+1)
    for j in range(len(bag)):
        s = list(map(lambda x,y: x+y, s, bag[j]))
    for j in range(1,m+1):
        if not s[j] >= x:
            break
    else:
        ans.append(s[0])
if ans == []:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
import itertools

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

ans = 10**8

for i in range(2**N):
    score = [0] * M
    total = 0
    for j in range(N):
        if ((i >> j) & 1):
            total += a[j][0]
            for k in range(M):
                score[k] += a[j][k+1]
        
    if min(score) >= X:
        ans = min(ans, total)

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

Submission status: Accepted

Solution code:
import itertools

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

#かう１ 買わない0
a = [0,1]
Ls = list(itertools.product(a, repeat=N))
#print('Ls:', Ls)  #############

ans=100000000
for L in Ls:
    #print('L:            ', L)   #############
    cost=0
    rikai=[0]*(M+1)
    hon=0
    flag=0
    for l in L:
        #print('l,hon:',l,hon)
        if l==1:  #買うなら
            cost+=CA[hon][0]
            #print('CA[hon]:', CA[hon])
            for i in range(1,M+1):
                rikai[i]+=CA[hon][i]
            #print('rikai:', rikai)

        hon+=1

    #理解度X以上あるかcheck
    #print('rikai, cost:', rikai,cost)
    for i in range(1,M+1):
        if rikai[i]<X:  #理解度X未満があったら
            flag=1
    #print('flag:', flag)
    if flag==0:  #理解度すべてX以上
        ans=min(ans,cost)
    else:  #理解度X未満
        continue
if ans==100000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n,m,x=map(int, input().split())
sl=[]
pl=[]
for k in range(n):
  book=list(map(int,input().split()))
  sl.append(book[1:])
  pl.append(book[0])
  
sl=np.array(sl)
ans=10**8

for i in range(2**n):
  skill=np.zeros(m)
  price=0
  for j in range (n):
    if ((i>>j)&1):
      skill+=sl[j]
      price+=pl[j]
  bottom=np.amin(skill)
  if bottom>=x and price<ans:
    ans=price
if ans==10**8:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

def dfs(i, ais, cur):
	if i == len(ais): return 0 if all([e<=0 for e in cur]) else +float('inf')
	return min( ais[i][0] + dfs(i+1 , ais, [c - ais[i][j+1] for j,c in enumerate(cur)]), dfs(i+1, ais, cur))

r = dfs(0,ais,[x] * m) 
print r if r < float('inf') else -1

Submission status: Accepted

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

ans=float('inf')

for i in range(1<<n):
    cost_sun=0
    rikaido=[0]*m
    for j in range(n):
        if(i>>j)&1:
            cost_sun+=c[j]
            for k in range(m):
                rikaido[k]+=a[j][k]
    
    isOK=True
    for j in range(m):
        if rikaido[j]<x:
            isOK=False
            break
    if isOK:
        ans=min(ans, cost_sun)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
lst = []
for i in range(n):
  lst.append(list(map(int, input().split())))
pmin = 10 ** 10
for i in range(1, 2 ** n): # 選び方
  sbin = format(i, 'b')
  sbin = '0' * (n - len(sbin)) + sbin
  temp = [0] * m
  p = 0
  for j in range(n): # 選ぶ行
    if sbin[j] == '1':
      for k in range(m): # 足す
        temp[k] += lst[j][k + 1]
      p += lst[j][0]
  if min(temp) >= x:
    pmin = min(pmin, p)
if pmin == 10 ** 10:
  print(-1)
else:
  print(pmin)

Submission status: Accepted

Solution code:
import numpy as np

n,m,x=map(int,input().split())
c=[]
a=[]
ans=10**8

for k in range(n):
  line=list(map(int,input().split()))
  c.append(line[0])
  a.append(line[1:])

a=np.array(a)


for i in range(2**n):
  level=np.zeros(m)
  price=0
  for j in range(n):
    if ((i>>j)&1):
      level+=a[j]
      price+=c[j]
  bottom=int(np.amin(level))
  if bottom>=x and price<ans:
    ans=price
if ans==10**8:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
c_list = []
a_list = []
for i in range(N):
    tmp = list(map(int, input().split()))
    c_list.append(tmp.pop(0))
    a_list.append(tmp)

cost = 100000000000
flg = False
for cnt in range(2 ** N):
    cost_tmp = 0
    score_tmp = [0] * M
    cnt_str = format(cnt, 'b')
    cnt_str = cnt_str[::-1]
    
    for i in range(len(cnt_str)):
        if(cnt_str[i] == '1'):
            cost_tmp += c_list[i]
            for j in range(M):
                score_tmp[j] += a_list[i][j]
    if(sum(x >= X for x in score_tmp) == M):
        cost = min(cost, cost_tmp)
        flg = True

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

Submission status: Accepted

Solution code:
import numpy as np

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

def is_ok(mask):
    if not np.any(mask):
        return False
    return np.all(np.sum(A[mask], axis=0)>=X)

ans = np.inf
for bit_mask in range(2**N):
    mask = [bool((bit_mask >> i) & 1) for i in range(N)]
    if is_ok(mask):
        ans = min(ans, sum(C[mask]))
print(ans if ans!=np.inf else -1)

Submission status: Accepted

Solution code:

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

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

ans = 10**10
for bit in range(1<<N):
    sum_p = 0
    p = [ 0 for _ in range(M) ]
    for i in range(N):
        if bit & 1<<i:
            for j, a in enumerate(A[i]):
                p[j] = p[j] + a
            sum_p = sum_p + C[i]

    n = sum( x >= X for x in p )
    if n == M:
        ans = min(ans, sum_p)

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
C = []
A = []
for n in range(N):
    l = list(map(int,input().split()))
    C.append(l[0])
    A.append(l[1:len(l)])
l = [0] * (N + 1)
Mx = 10 ** 7
Mn = Mx
while True:
    i = 0
    while True:
        l[i] = l[i] ^ 1
        if l[i] == 1:
            break
        i += 1
    if i >= N:
        break
    lA = [0] * M
    c = 0
    for n in range(N):
        if l[n] == 0:
            continue
        c += C[n]
        for m in range(M):
            lA[m] += A[n][m]
    flg = True
    for m in range(M):
        if lA[m] < X:
            flg = False
            break
    if not flg:
        continue
    if c < Mn:
        Mn = c
if Mn == Mx:
    print(-1)
else:
    print(Mn)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
list_CA = [ list(map(int,input().split(" "))) for _ in range(n)]
ans = pow(10, 10)

for i in range(2**n):
    l = [0]*m
    h = 0
    for j in range(n):
        if ((i >> j) & 1):
            for p in range(m):
                l[p] += list_CA[j][p+1]
            h += list_CA[j][0]
    cnt = 0
    for k in l:
        if k >= x:
            cnt += 1
    if cnt == m:
        ans = min(ans, h)

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = []
s = [0 for i in range(2 ** n)]
for i in range(2 ** n):
    tmp_0 = [0]
    tmp_1 = [0 for i in range(m)]
    for j in range(n):
        if ((i >> j) & 1):
            tmp_0[0] += a[j][0]
            for k in range(1,m+1):
                tmp_1[k-1] += a[j][k]
    #print(tmp_1)
    if min(tmp_1) >= x:
        ans.append(tmp_0[0])

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