Problem:


Score : 300 points

Problem

Takahashi, who is a novice in competitive programming, wants to learn M algorithms.
Initially, his understanding level of each of the M algorithms is 0.

Takahashi is visiting a bookstore, where he finds N books on algorithms.
The i-th book (1\leq i\leq N) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j-th algorithm will increase by A_{i,j} for each j (1\leq j\leq M).
There is no other way to increase the understanding levels of the algorithms.

Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

0\leq A_{i, j} \leq 10^5

Input

Input is given from Standard Input in the following format:

N M X
C_1 A_{1,1} A_{1,2} \cdots A_{1,M}
C_2 A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
C_N A_{N,1} A_{N,2} \cdots A_{N,M}

Output

If the objective is not achievable, print -1; otherwise, print the minimum amount of money needed to achieve it.

Sample Input 1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

Sample Output 1

120

Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.

Sample Input 2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

Sample Output 2

-1

Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.

Sample Input 3

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

Sample Output 3

1067



Sample input:
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9


Sample output:
120

Submission status: Accepted

Solution code:
from itertools import combinations
N, M, X = map(int, input().split())
books = []
for _ in range(N):
    books.append(list(map(int, input().split())))
P = []
for i in range(1, N+1):
    for item in list(combinations(books, i)):
        P.append(item)
ans = 10 ** 9 + 1
for items in P:
    price = 0
    chk = [0] * M
    for p in items:
        price += p[0]
        for i, item in enumerate(p[1:]):
            chk[i] += item
        if all(c >= X for c in chk):
            ans = min(ans, price)
            break
if ans == 10 ** 9 + 1:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
def roots(l,i,v,ans):
    if i<len(l):
        roots(l,i+1,v,ans)
        roots(l,i+1,v+[l[i]],ans)
        return
    else:
        if v!=[]:
            ans.append(v)
        return ans

def sumL(l):
    ans=[0]*len(l[0])
    for i in range(len(l)):
        for j in range(len(l[i])):
            ans[j]+=l[i][j]
    return ans

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

ans=[]
roots(l,0,[],ans)

minV=10**10

for i in ans:
    flag=True
    s=sumL(i)
    for j in s[1:]:
        if j<x:
            flag=False
            break
    if flag and minV>s[0]:
        minV=s[0]
if minV==10**10:
    print(-1)
else:
    print(minV)

Submission status: Accepted

Solution code:
import math

N, M, X = (int(x) for x in input().split())
comp = [0] * M
CA = []
for i in range(N):
    CA.append(list(map(int,input().split())))


minimum = 10 ** 5 * 14
for i in range(2**N):
    comp = [0] * (M + 1)
    for j in range(N):
        if (i >> j) & 1:
            comp = [x + y for (x, y) in zip(comp, CA[j])]
    flag = True
    for j in range(M + 1):
        if j == 0:
            continue
        if comp[j] < X:
            flag = False
            break
    if minimum > comp[0] and flag:
        minimum = comp[0]

if minimum == 10 ** 5 * 14:
    minimum = -1
print(minimum)

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from operator import add

N,M,X = map(int, input().split())		# 5 7 2
CA = [list(map(int, input().split())) for _ in range(N)]		#=> [[1, 0], [2, 10], [3, 210], [4, 3210]]

A=[]
C=[]
for n in range(N):
	C.append(CA[n][0])
	A.append(CA[n][1:])


ans = sum(C)+1
for i in range(1 << N):

	tmpA = [0]*M
	c = 0
	
	for j in range(N):
		if ((i >> j) & 1) == 0: continue

		tmpA = map(add, tmpA, A[j])
		c += C[j]
	
	if min(tmpA) < X: continue
	
	ans = min(ans, c)


print( ans if ans <= sum(C) else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
a = [[]for i in range(n)]
ans = -1
for i in range(n):
    a[i] = list(map(int,input().split()))
for i in range(2**n):
    b = str(bin(i))
    c = [0]*(m+1)
    cscore = 0
    for j in range(0,len(b)-2):
        if b[-j-1] == "1":
            for k in range(m+1):
                c[k]+=a[j][k]
    cscore = c[0]
    for j in range(m):
        if c[j+1] < x:
            cscore = -1
    if cscore!=-1:
        if ans == -1:
            ans = cscore
        else:
            ans = min(ans,cscore)

print(ans)

Submission status: Accepted

Solution code:
import sys

lines = sys.stdin.readlines()
N, M, X = map(int, lines[0].split())
A = []
C = []

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

# return []
def full_search():
    costs = []
    for i in range(2**N):
        vals = [0] * M
        cost = 0

        # iを二進数に直して扱う。それぞれのビットがn冊目の本を買うかどうかに匹敵。
        for j in range(N):
            # ビットを移動しながらn冊目の本を買う際のコストと経験値を計算する
            if ((i >> j) & 1):
                # 現在の組み合わせに対して
                # 全てのアルゴリズム分を計算
                cost += C[j]

                # 全てのアルゴリズム(m)に対して経験値を求める
                for m in range(M):
                    vals[m] += A[j][m]

        combination_ok = True
        for m in range(M):
            if vals[m] >= X:
                continue
            else:
                combination_ok = False
                break

        if combination_ok:
            costs.append(cost)
    return costs

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

Submission status: Accepted

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

INF = 10**9
ans = INF
# シフトで2^nまで全探索
# 全ての組み合わせに対してforを回す
# 部分集合を全探索するならbit全探索
# 左シフト<< 桁を左にずらし，0を入れていく
for s in range(0, 1 << N):
    # 習得度をいれるリストを定義
    smart = [0] * M
    cost_sum = 0
    # sには一旦10進数が入る
    # 得られた１組あわせに対して，2進数でそのitemを用いているかを (s >> i) & 1で確認する
    # これは，右シフト
    # 012のループ
    for i in range(N):
        # 買っているかを
        if (s >> i) & 1:
            cost_sum += C[i]
            for j in range(M):
                smart[j] += A[i][j]
    ok = True
    if min(smart) < X:
        ok = False
    if ok:
        ans = min(ans, cost_sum)

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

cost = []

skill = list(zip(*CA))

for i in range(1, M+1):
    if sum(skill[i]) < X:
        print(-1)
        exit()

for i in range(1, N+1):
    for balls in list(itertools.combinations(CA, i)):
        test = np.zeros(M+1)
        for j in balls:
            jtest = np.asarray(j)
            test = test + jtest

        if min(test[1:])>=X:
            cost.append(test[0])

print(int(min(cost)))

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
C = []
A = np.ndarray((N, M), dtype=int)
for j in range(N):
    c, *a = [int(i) for i in input().split()]
    C.append(c)
    A[j] = a

ans = 10**20
for i in range(2 ** N):
    cost = 0
    sk = np.zeros(M, dtype=int)
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            cost += C[j]
            sk += A[j, :]
    if all(s >= X for s in sk):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import itertools
import sys

N, M, X  = map(int, input().split())
money = []
A = []
ans = []
for _ in range(N):
    nums = [int(x.strip()) for x in input().split(' ') ]
    money.append(nums[0])
    nums.pop(0)
    A.append(nums)
num_money = []
for index, num in enumerate(money):
    num_money.append(index)
    
def run(lis, num, A, X, M, ans, money):
    ans_list = []
    for team in itertools.combinations(lis, num):
        count = 0
        for i in range(M):
            tmp = 0
            for j in list(team):
                tmp += A[j][i]
            if tmp >= X:
                count += 1
        if count == M:
            tmp_ans = []
            for n in list(team):
                tmp_ans.append(money[n])
            ans_list.append(sum(tmp_ans))
    if not len(ans_list) == 0:
        ans.append(min(ans_list))
    
    return ans
        
for i in range(1, N+1):
    ans = run(num_money, i, A, X, M, ans, money)
    
if not len(ans) == 0:
    print(min(ans))
    
else:
    print(-1)

Submission status: Accepted

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

ans=10**9
for i in range(2**n):
  t_ans=0
  us=[0 for j in range(m)]
  for k in range(n):
    if (i>>k)&1:
      book=l[k]
      t_ans+=book[0]
      for p in range(m):
        us[p]+=book[p+1]

  if min(us)>=x:
    ans=min(ans,t_ans)

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

Submission status: Accepted

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

INF = 10**9
ans = INF
# シフトで2^nまで全探索
for s in range(0, 1 << N):
    # 習得度をいれるリストを定義
    smart = [0] * M
    cost_sum = 0
    # sには10進数が入る
    for i in range(N):
        # 買っていない時
        if (s >> i) % 2 == 0: continue
        cost_sum += C[i]
        for j in range(M):
            smart[j] += A[i][j]
    ok = True
    if min(smart) < X:
        ok = False
    if ok:
        ans = min(ans, cost_sum)

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

Submission status: Accepted

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

ans=10**9
for i in range(2**n):
  t_ans=0
  us=[0 for j in range(m)]
  for k in range(n):
    if (i>>k)&1:
      book=l[k]
      t_ans+=book[0]
      for p in range(m):
        us[p]+=book[p+1]

  if all([q>=x for q in us]):
    ans=min(ans,t_ans)

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

Submission status: Accepted

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

c = [0 for _ in range(n)]
A = [0 for _ in range(n)]
for i in range(n):
	line = [int(j) for j in input().split()]
	c[i] = line[0]
	A[i] = line[1:]

ans = 100111000010

for s in range(1<<n):
	alg = [0 for _ in range(m)]
	cost = 0
	judge = True
	for i in range(n):
		if s>>i&1:
			cost += c[i]
			for j in range(m):
				alg[j] += A[i][j]

	for j in range(m):
		if alg[j] < x:
			judge = False
	
	if judge:
		ans = min(cost, ans)

if not judge:
	print(-1)
else:
	print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
ans = float('inf')

for i in range(2**n):
    sum = [0]*(m+1)
    # n桁について調査
    for j in range(n):
        # iのj桁目が1かどうかcheck
        if (i >> j) & 1:
            for k in range(m+1):
                sum[k] += l[j][k]
    if sum[0] < ans:
        for a in range(1,m+1):
            if sum[a] < x:
                break
        else:
            ans = sum[0]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
n, m, x = map(int, input().split())
C = [0] * n
A = [[0] * m for i in range(n)]

mlist = [0] * m
for i in range(n):
    books = list(map(int, input().split()))
    C[i] = books[0]
    for j in range(m):
        A[i][j] = books[j + 1]

mincost = sys.maxsize
for i in range(2**n):
    sumlist = [0] * m
    currentcost = 0
    for j in range(n):
        if ((i >> j) % 2) == 1:
            for k in range(m):
                sumlist[k] += A[j][k]
            currentcost += C[j]
    if min(sumlist) >= x:
        if currentcost < mincost:
            mincost = currentcost

if mincost == sys.maxsize:
    print("-1")
else:
    print(mincost)

Submission status: Accepted

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

import copy
result = []
def test(i,i_sum,cost):
    
    flag = 0
    if i <= n:
        for j in range(m):
            if i_sum[j] < x:
                flag = 1
                break

        if flag == 1:
                test(copy.deepcopy(i)+1, i_sum[:],cost[:])#参考書を使わない場合

                for j in range(1,m+1):#参考書を使う場合
                    i_sum[j-1] += sp[i-1][j]
                cost[0] += sp[i-1][0]
                test(copy.deepcopy(i)+1, i_sum[:],cost[:])
        else:
            result.append(cost[0])
test(0,[0]*m,[0])

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

Submission status: Accepted

Solution code:
from itertools import compress

import numpy as np

N, M, X = [int(x) for x in input().split()]
CA = np.array([[int(x) for x in input().split()] for _ in range(N)])

minimal_cost = None
for bought_book in range(1, 2**N):
    bought_book = [int(b) for b in ("{:0" + str(N) + "b}").format(bought_book)]

    CA_filtered = np.array(list(compress(CA, bought_book)))

    total_cost = sum(CA_filtered[:, 0])
    total_understanding = np.sum(CA_filtered[:, 1:], axis=0) >= X
    if np.all(total_understanding):
        minimal_cost = min(minimal_cost or total_cost, total_cost)

print(minimal_cost if minimal_cost is not None else "-1")

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,X = map(int, readline().split())
data = np.array(read().split(), np.int64)

data = data.reshape(N,-1)
C = data[:,0]
A = data[:,1:]

cost = np.zeros(1<<N, np.int64)
ability = np.zeros((1<<N, M), np.int64)
for i in range(N):
    cost[1<<i:1<<(i+1)] = cost[:1<<i] + C[i]
    ability[1<<i:1<<(i+1)] = ability[:1<<i] + A[i]

ok = np.all(ability >= X, axis=1)

x = cost[ok]
answer = -1 if len(x) == 0 else x.min()
print(answer)

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int,input().split())
c=[]
for i in range(n):
  c.append(list(map(int,input().split())))
#print(c)

ans = 9999999999

for el in itertools.product([0,1],repeat=n):
  # 達成可能性の判定
  cav = [0]*(m+1)
  for i in range(n):
    if el[i] == 1:
      for j in range(m+1):
        cav[j] += c[i][j]

  if x > min(cav[1:m+1]):
    pass
  else:
    ans = min(cav[0],ans)

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

Submission status: Accepted

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

a = [[int(i) for i in input().split()] for _ in range(n)] #行列
#s = [int(input()) for _ in range()] #縦
#a = [int(x) for x in input().split()] #横

sum1 = [0] * (m+1)
sum2 = [0] * (m+1)

ans = 0

st = list(itertools.product([0,1], repeat = n))
#print(st)

for i in range(n):
    for j in range(m+1):
        sum1[j] += a[i][j]
for  i in range(1,m+1):
    if sum1[i] < x:
        sum1[0] = -1
        print(-1)
        exit()

ans = sum1[0]

for i in range(2**n):
    for j in range(n):
        for k in range(m+1):
            #print(i,j,k)
            sum2[k] +=  a[j][k]*st[i][j]
    #print(sum2)
    for i in range(1,m+1):
        if sum2[i]  < x:
            sum2[0]= 100000000
    ans = min(sum2[0],ans)
    #print(ans)
    sum2 = [0] * (m+1)

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())))
ans=10000000
for i in range(2**N):
  score=[0]*M
  coin=0
  for j in range(N):
    if i>=2**(N-1-j):
      for p in range(M):
        score[p]+=l[j][p+1]
      coin+=l[j][0]
      i-=2**(N-1-j)
  flag=0
  for q in range(M):
    if score[q]<X:
      flag=1
  if flag==0:
    if ans>coin:
      ans=coin
if ans==10000000:
  print("-1")
else:
  print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N, M, X = map(int, input().split())

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

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

ans = float("INF")
p = [i for i in range(1, N+1)]

for k in range(1, N+1):
  for v in combinations(p, k):
    smart = [0] * M
    cost_sum = 0
    for i in v:
      cost_sum += C[i-1]
      for j in range(M):
        smart[j] += A[i-1][j]
    ok = True
    for j in range(M):
      if smart[j] < X:
        ok = False
    if ok:
      ans = min(ans, cost_sum)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


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


def dfs(asum, b):
    global N, M, X
    rst = 10 ** 8
    if b == N:
        if all(asum[i] >= X for i in range(1, M + 1)):  # check関数は all で代替可能
            rst = asum[0]
    else:
        # b番目を買わない場合
        rst = min(rst, dfs(asum, b + 1))
        
        # b番目を買う場合
        asum2 = tuple(asum[i] + C[b][i] for i in range(M + 1))  # tashi関数を普通に書くならこうかな、、tupleにキャストする。
        rst = min(rst, dfs(asum2, b + 1))

    return rst


rst = dfs(tuple([0] * (M + 1)), 0)
ans = rst if rst < 10 ** 8 else -1
print(ans)

Submission status: Accepted

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

N,M,X = map(int,readline().split())
data = [None] * N
for i in range(N):
  d = list(map(int,input().split()))
  c = d[0]
  target = d[1:]
  data[i] = [c,target]

ans = 10 ** 9
for i in range(2 ** N):
  cost = 0
  skills = [0] * M
  for j in range(N):
    if (i >> j) & 1:
      cost += data[j][0]
      for k in range(len(data[j][1])):
        skills[k] += data[j][1][k]
  if ans > cost:
    for k in range(len(skills)):
      if skills[k] < X:
        break
    else:
      ans = cost
      
if ans == 10 ** 9:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

C=[]
A=[]
for n in range(N):
  AC=list(map(int,input().split()))
  C.append(AC[0])
  A.append(AC[1:])
ans=10**9

for n in range(2**N):
  total=0
  und=[0]*M
  for j in range(N):
    if n >> j & 1:
      total+=C[j]
      for m in range(M):
        und[m]+=A[j][m]
  if X <= min(und):
    ans=min(total,ans)
if ans==10**9:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
c=[0]*n
a=[0]*n
ans=10**10
for i in range(n):
  d,*b=map(int,input().split())
  c[i]=d
  a[i]=b
import numpy as np
a=np.array(a)
from itertools import product
r=list(product([0,1],repeat=n))
for i in r:
  tmp=np.array([0]*m)
  cost=0
  for j,k in enumerate(i):
    tmp+=k*a[j]
    cost+=k*c[j]
  if all(tmp>=x):
    ans=min(ans,cost)
if ans>10**9:
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M, X= list(map(int,input().split()))
l = list(itertools.product([0,1], repeat=N))

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

r = float('inf')
for i in l:
  cost = 0
  i = np.array(i).reshape( N,-1)
  f = i*C
  sum_f = f.sum(axis = 0)
  
  if all(sum_f[1:]>=X):
    if r >sum_f[0] :
      r = sum_f[0]
    
if r == float('inf') :
  print(-1)
else :
  print(r)

Submission status: Accepted

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

ans = 10 ** 18
for bit_state in range(1 << n):
    tmp = [0] * m
    cost = 0
    for i in range(n):
        if bit_state & (1 << i):
            for j in range(m):
                tmp[j] += info[i][j + 1]
            cost += info[i][0]

    for j in range(m):
        if tmp[j] < x:
            break
    else:
        ans = min(cost, ans)

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

Submission status: Accepted

Solution code:
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,X = LI()
CA = np.array([LI() for _ in range(N)])
ans = float('INF')
for i in range(2**N):
    bit = np.array([[i>>j&1 for j in range(N)]]).T
    t = np.sum(CA*bit,axis=0)
    if np.all(t[1:]>=X):
        ans = min(ans,t[0])
print(ans if ans !=float('INF') else -1)

Submission status: Accepted

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

ans = 10**18

for b in range(2**N):
  b = bin(b)[2:].zfill(N)
  pay = [0]*(M+1)
  count = 0
  for i in range(N):
    if b[i] == "1":
      pay = [x + y for (x, y) in zip(pay, l[i])]
  for j in range(1,M+1):
    if pay[j] >= X:
      count += 1
  if count == M:
    ans = min(ans,pay[0])
if ans != 10**18:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
from itertools import product
n, m, x = map(int, input().split())
ca = [tuple(map(int, input().split())) for _ in range(n)]
INF = 10**18
ans = INF
for i in product([0, 1], repeat=n):
    cost = 0
    smart = [0]*m
    for j in range(n):
        if i[j] == 0:
            continue
        c, *a = ca[j]
        cost += c
        for k in range(m):
            smart[k] += a[k]

    if all(x <= y for y in smart):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N, M, X = map(int, input().split())
items = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int32)

out = 10**18
for c in itertools.product([False, True], repeat=N):
    tmp = np.sum(items[np.where(c)], axis=0)
    if np.any(tmp):
      if M == np.count_nonzero(tmp[1:] >= X):
        out = min(out, tmp[0])
if out == 10**18:
  print(-1)
else:
  print(out)

Submission status: Accepted

Solution code:
# coding:utf-8
# bit全探索
n, m, x = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(n)]
ans = 12 * (10 ** 5) + 1

for bit in range(2 ** n):
    tmp_book = [0] * m
    price = 0
    for i in range(n):
        if ((bit >> i) & 1):
            price += book[i][0]
            for j in range(m):
                tmp_book[j] += book[i][j + 1]
    if all(item >= x for item in tmp_book):
        ans = min(price, ans)

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

Submission status: Accepted

Solution code:
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,X = LI()
CA = np.array([LI() for _ in range(N)],dtype=int)
ans = float('INF')
for i in range(2**N):
    bit = np.array([[i>>j&1 for j in range(N)]]).T
    t = np.sum(CA*bit,axis=0)
    if np.all(t[1:]>=X):
        ans = min(ans,t[0])
print(ans if ans !=float('INF') else -1)

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,C, A):
    min_cost = ''
    combs = set()
    for i in range(N):
        for c in combinations(range(N), i+1):
            combs.add(c)

    for comb in combs:
        cost = 0
        xs = [0 for _ in range(M)]
        for c in comb:
            for i in range(M):
                xs[i] += A[c][i]
            cost += C[c]

        if all([x>=X for x in xs]):
            min_cost = cost if min_cost =='' else min(min_cost, cost)

    if min_cost != '':
        print(min_cost)
    else:
        print(-1)

    pass

if __name__ == '__main__':
    C = []
    A = []
    N, M, X = list(map(int, input().split()))
    for n in range(N):
        lst = list(map(int, input().split()))
        # for m in range(M):
        
        c = lst[0]
        a = lst[1:]

        C.append(c)
        A.append(a)

    
    main(N,M,X,C, A)

Submission status: Accepted

Solution code:
n, m, x = map(int,input().split())
c = [list(map(int, input().split())) for i in range(n)]
ans = float('inf')
money = [float('inf')]

for i in range(2**n):
  temp_money = 0
  temp_skill = [0]*m
  for j in range(n):
    if (i >> j) & 1:
      temp_money += c[j][0]
      temp_skill = [a + b for a, b in zip(temp_skill, c[j][1:m+1])]
    if all([i >= x for i in temp_skill])==True:
      money.append(temp_money)

ans = min(ans,min(money))
if ans == float("inf"):
  ans = -1

print(ans)

Submission status: Accepted

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

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

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

ans = float("INF")
for bit in range(0, 1 << N):
  smart = [0] * M
  cost_sum = 0
  for i in range(N):
    if (bit >> i) % 2 == 0:
      continue
    cost_sum += C[i]
    for j in range(M):
      smart[j] += A[i][j]
  ok = True
  for j in range(M):
    if smart[j] < X:
      ok = False
  if ok:
    ans = min(ans, cost_sum)

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

Submission status: Accepted

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

oklst = []
for n in range(1,N+1):
    for lst in itertools.combinations(ca_lst,n):
        tmp = sum(lst)
        for i in tmp[1:]:
            if i < X:
                break
        else:
            price = 0
            for m in lst:
                price += m[0]
            oklst.append(price)
if len(oklst) > 0:
    print(min(oklst))
else:
    print(-1)

Submission status: Accepted

Solution code:

a = [[0]*12 for _ in range(12)]

INF = 1 << 29

def main():
    # input
    n, m, x = map(int, input().split())
    c = [0]*n
    for i in range(n):
        tmp = list(map(int, input().split()))
        c[i] = tmp[0]
        for j in range(m) :
            a[i][j] = tmp[j+1]

    # どの本を買うか、買わないかを２進数で表す（その状態と１０進数を1対１に対応させてる）
    # 例えば１の時001、２の時010みたいに各bitがその本iを買うなら１、買わないなら０
    ans = INF
    for bit in range(2**n) :
        cost = 0
        d = [0]*m # 各アルゴリズムの理解度をいれる配列
        for i in range(n): #　このループで２進数表現に直して、各桁の１を買った本と対応させてる
            # bitのi番目のbitが立ってる時に入る
            # & 1でシフトしたときにフラグが立っていたら入る。
            # bit(10進数)を2進数で表現したときにi桁目に１が入っていたらTrueを返す
            if (bit>>i&1):
                cost += c[i]
                for j in range(m) :
                    d[j] +=  a[i][j]

        ok = True
        for j in range(m) :
            if d[j] < x: # 各アルゴリズムで理解度がx以下のがあればFalseな組み合わせ
                ok = False

        if ok:
            ans = min(ans, cost)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
n, m, x = [int(x) for x in input().split()]
a = np.stack([np.array(input().split(), dtype=int) for _ in range(n)])
tot = np.sum(a, axis=0)
if min(tot[1:]) < x:
    print(-1)
    exit(0)
cost = tot[0]
whole = np.array(list(product([0,1],repeat=n)), dtype=bool)[1:-1]
for flag in whole:
    tot = np.sum(a[flag], axis=0)
    if min(tot[1:]) >= x and tot[0] < cost:
        cost = tot[0]
print(cost)

Submission status: Accepted

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

def rec(i, rikai, cost):

  flag = True
  for r in rikai:
    if r <= 0: continue
    else: flag = False
  if flag:
    return cost
  if i == N:
    return 10000000000000
  
  use_rikai = [ rikai[j] - arr[i][j+1] for j in range(M) ]
  use_cost = cost + arr[i][0]
  return min(rec(i+1, use_rikai, use_cost), rec(i+1, rikai,cost))

rikai = [X for j in range(M)]
res = rec(0, rikai, 0)
if res >= 10000000000000:
  print(-1)
else: print(res)

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N, M,X = isRaw()
    CAs = [isRaw() for n in range(N)]
    ans = INF
    for dbit in range(2**N):
        cb = [(dbit & (1 << n)) for n in range(N)]
        flg = 1
        for m in range(M):
            x = sum([CAs[n][m+1] for n in range(N) if cb[n]])
            if x<X:
                flg=0
                break
        if flg == 1:
            cost = sum([CAs[n][0] for n in range(N) if cb[n]])
            ans = min(ans,cost)
    return ans if ans!=INF else -1


print(main())

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, X = MAP()
C = [0] * N
A = [[]] * N
for i in range(N):
    C[i], *A[i] = MAP()

ans = INF
for bit in range(1<<N):
    skills = [0] * M
    cost = 0
    for i in range(N):
        if bit>>i & 1:
            cost += C[i]
            for j in range(M):
                skills[j] += A[i][j]
    if min(skills) >= X:
        ans = min(ans, cost)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N,M,X = map(int,input().split())
arr = [np.array(list(map(int,input().split()))) for _ in range(N)]
ans = float('inf')
for i in range(2**N):
  arr_sum = np.array([0]*(M+1))
  for j in range(N):
    if i>>j&1:
      arr_sum += arr[j]
  if np.all(arr_sum[1:]>=X):
    ans = min(ans,arr_sum[0])

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