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:
n,m,x = map(int,input().split())
book = []
import numpy as np
for _ in range(n):
    a = list(map(int,input().split()))
    book.append(a)
ans = float("inf")
for i in range(1,2**n):
    use_book = []
    for j in range(n):
        if (i>>j) &1:
            use_book.append(book[j])
    arr = np.array(use_book)
    arr_sum = np.sum(arr,axis =0)
    true =1
    for i in range(1,m+1):
        if arr_sum[i] < x:
            true = 0
            break
    if true == 1:
        ans = min(ans,arr_sum[0])
if ans == float("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)]

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 = list(map(int, input().split()))
c = []
alg = []
for i in range(n):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    tmp.pop(0)
    alg.append(tmp)

price_min = -1

for i in range(2**n):
    price = 0
    skill = [0]*m
    skillFlag = True
    buyBin = format(i, '0'+str(n)+'b')
    for j in range(n):
        if buyBin[j] == '1':
            price += c[j]
            for k in range(m):
                skill[k] += alg[j][k]

    for k in range(m):
        if skill[k] < x:
            skillFlag = False
    
    if skillFlag:
        if price_min > price or price_min == -1:
            price_min = price

print(price_min)

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
C = []
A = [[] for i in range(M)]
resC = []
resA = list(A)

NEW = 0

def update(base):
  #print(NEW,base)
  if base==None:
    return NEW
  return base + NEW

def check(num):
  return num>=X

def check2(*args):
  res = True
  for val in args:
    buf = (val >= X)
    res = res and buf
  return res

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

for i in range(N):
  if i == 0:
    NEW = C[i]
    resC = [0, NEW]
    resA = [[0, A[j][i]] for j in range(M)]
  else:
    NEW = C[i]
    resC = resC + list(map(update, resC))
    for j in range(M):
      NEW = A[j][i]
      resA[j] = resA[j] + list(map(update, resA[j]))

res = list(map(check2, *resA))
#print(np.asarray(resC)[res]) 
if sum(res)==0:
  print(-1)
else:
  print(min(np.asarray(resC)[res]))

Submission status: Accepted

Solution code:
import itertools
import numpy as np

def calc(aaa, M, X, pattern):
    tmp_price = 0
    for t in pattern:
        price = 0
        sum = np.zeros(M)
        for i in t:
            price += aaa[i][0]
            current = np.array(aaa[i][1:M+1])
            sum = sum + current

        if np.count_nonzero(sum >= X) >= M:
            if tmp_price == 0:
                tmp_price = price
            else:
                tmp_price = min(tmp_price, price)
    
    return tmp_price


def solve(N, M, X, aaa):
    tmp_result = 0
    for i in range(N):
        pattern = list(itertools.combinations(range(N), i + 1))
        result = calc(aaa, M, X, pattern)
        if result > 0:
            if tmp_result == 0:
                tmp_result = result
            else:
                tmp_result = min(tmp_result, result)

    if tmp_result != 0:
        return tmp_result
    else:
        return -1

N, M, X, *A = map(int, open(0).read().split())

aaa = []
aa = []
for index, x in enumerate(A):
    aa.append(x)
    if (index+1) % (M+1) == 0:
        aaa.append(aa)
        aa = []

print(solve(N, M, X, aaa))

Submission status: Accepted

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

keep=10**100
for i in range(0,2**n):
  rikai=[0]*m
  moji=""
  calc=i
  res=0
  for j in range(0,n):
    j=n-1-j
    onezero=calc//(2**j)
    moji+=str(onezero)
    calc-=onezero*(2**j)
  for k in range(0,n):
    if moji[k]=="1":
      res+=lis[k][0]
      for l in range(1,m+1):
        rikai[l-1]+=lis[k][l]
  prep=1
  for z in range(0,m):
    if rikai[z]<x:
      prep=0
  if prep==1:
    if res<keep:
      keep=res

      
if keep==10**100:
  print(-1)
else:
  print(keep)

Submission status: Accepted

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

c = []
d = []
for i in range(n):
	s = list(map(int, input().split()))
	d.append(s)
    
ans = 10**9
for i in range(1,n+1):
	for j in itertools.combinations(d,i):
		s = [0 for ii in range(m+1)]
		for k in j:
			for l in range(m+1):
				s[l] += k[l]
		y = min(s[1:])
		if y >= x:
			ans = min(ans,s[0])
            
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 = [[] for _ in range(n)]
for i in range(n):
    c[i], *a[i] = map(int, input().split())

ans = float(('inf'))
for s in range(1 << n):
    money = 0
    understand = [0] * m
    for i in range(n):
        if (1 << i) & s != 0:
            money += c[i]
            for j in range(m):
                understand[j] += a[i][j]
    if min(understand) >= x:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M, X = il()
    CA = [il() for _ in range(N)]

    ret = MAX
    for n in range(1 << N):
        k = 0
        A = [0] * M
        for j in range(N):
            c, *alist = CA[j]
            if n >> j & 1:
                k += c
                for i in range(len(alist)):
                    A[i] += alist[i]
            if all([a >= X for a in A]):
                ret = min(ret, k)
                break
        else:
            continue

    print(-1 if ret == MAX else ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
sys.setrecursionlimit(10**8)
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def main():
    N, M, X = map(int, input().split())
    C = [0]*N
    A = [None]*N
    for i in range(N):
        C[i], *A[i] = map(int, input().split())

    min_money = INF
    # 全探索
    for pattern in itertools.product((0, 1), repeat=N):
        # for i in range(1 << N):
        tot = [0]*M
        money = 0
        for i, use in enumerate(pattern):
            if use == 0:
                continue
            money += C[i]
            for j in range(M):
                tot[j] += A[i][j]

        if all(tot[j] >= X for j in range(M)):
            min_money = min(money, min_money)
    if min_money == INF:
        print(-1)
    else:
        print(min_money)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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


ans = -1
for i in range(pow(2, N)):
    cost = 0
    flag = [False for _ in range(M)]
    rikai = [0 for _ in range(M)]
    binary = format(i, '0{}b'.format(N))
    for index, value in enumerate(binary):
        if value == '1':
            cost += Z[index][0]
            for j in range(1, M+1):
                rikai[j -1] += Z[index][j]
                if rikai[j -1] >= X:
                    flag[j -1] = True
        if all(flag):
            if ans == -1:
                ans = cost
                continue
            ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools

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:])

minimum = 10**10
for i in range(2**n):
    cost = 0
    rikaido = [0]*m
    ok = True
    for j in range(n):
        if i >> j & 1:
            cost += c[j]
            for index in range(m):
                rikaido[index] += a[j][index]
    for k in range(m):
        if rikaido[k] < x:
            ok = False
    if ok:
        minimum = min(minimum, cost)

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

Submission status: Accepted

Solution code:

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

ans = -1
for i in range(2**n):
    li = [0]*(m+1)
    # print('＝＝＝＝＝＝＝＝＝＝')
    for j in range(n):
        # print('i = ', i)
        # print('j = ', j)
        # print('(i >> j) = ', (i >> j))
        # print('((i >> j) & 1) = ', ((i >> j) & 1))
        if ((i >> j) & 1):
            for k in range(m+1):
                li[k] += ca[j][k]
        # print('li = ', li)
    for j in range(1, m+1):
        if li[j] < x:
            break
    else:
        if ans == -1:
            ans = li[0]
        else:
            if ans > li[0]:
                ans = li[0]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)




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

    res_money = 1_000_000_000_000
    for i in range(2 ** n):
        op = [0] * n  # あらかじめ ["-", "-", "-"] というリストを作っておく
        for j in range(n):
            if ((i >> j) & 1):
                op[n - 1 - j] = 1  # フラグが立っていた箇所を "+" で上書き
        s = [0] * m
        money = 0
        for k in range(n):
            if op[k] == 0:
                continue
            money += c[k]
            for l in range(m):
                s[l] += a[k][l]
        ng = False
        for p in range(m):
            if s[p] < x:
                ng = True
                break
        if not ng:
            if res_money > money:
                res_money = money

    if res_money != 1_000_000_000_000:
        print(res_money)
    else:
        print(-1)



main()

Submission status: Accepted

Solution code:
n,m,x=[int(j) for j in input().split()]
l=[]
import numpy as np
for i in range(n):
    tmp=[int(j) for j in input().split()]
    l.append((tmp[0],np.array(tmp[1:])))
ans=10**18
import itertools
for i in itertools.product(range(2),repeat=n):
    tl=np.array([0]*m)
    tc=0
    for idx,j in enumerate(i):
        if j==1:
            c,ll=l[idx]
            tc+=c
            tl+=ll
    if len(tl[tl>=x])==m:
        ans=min(ans,tc)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

def list_add(in1,in2):
    wrk = np.array(in1) + np.array(in2)
    return wrk.tolist()

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

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


for i in range(M):
    und_sum = 0
    for j in range(N):
        und_sum += book[j][i+1]
    if und_sum < X:
        print(-1)
        sys.exit()

min_money = 1000000000000000000
for i in range(2**N):
    if i == 0:
        continue
    flag_ok = 1
    buy = []
    for j in range(N):
        if((i>>j)&1):
            buy.append(j)
    sum = []
    for k in range(len(buy)):
        if k == 0:
            sum = book[buy[k]]
        else:
            sum = list_add(sum,book[buy[k]])
    for k in range(M):
        if sum[k+1] < X:
            flag_ok = 0
            break
    if flag_ok == 1:
        if min_money > sum[0]:
            min_money = sum[0]
    flag_ok = 1

print(min_money)

Submission status: Accepted

Solution code:
big_int = 10 ** 9

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

L = [0 for i in range(N)]
for i in range(N):
  L[i] = tuple(map(int, input().split()))

def foo(i):
  t = i
  T = [0 for j in range(M+1)]
  for j in range(N):
    for k in range(M+1):
      T[k] += L[j][k] * (t%2)
    t //= 2
  for k in range(1,M+1):
    if T[k] < X:
      return big_int
  return T[0]
  
ans = big_int

for i in range(2**N):
  ans = min(ans, foo(i))
  
if ans == big_int:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

C = []
A = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    C.append(tmp[0])
    A.append(tmp[1:])
    
f_inf = float("inf")    
ans = f_inf
for s in range(1<<n):
    cst = 0
    D = [0] * m
    for i in range(n):
        if s>>i & 1:
            cst += C[i]
            for j in range(m):
                D[j] += A[i][j]
    
    flg = True
    for d in D:
        if d < x: flg = False
    if flg: ans = min(ans, cst)

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

Submission status: Accepted

Solution code:
def ip():return list(map(int,input().split()))

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

ans=12*10**5+1
for i in range(1,2**n):
    f=bin(i)[2:]
    sum=[0]*m
    while len(f)<n:f='0'+f
    s=0
    for j in range(n):
        if f[j]=='1':
            s+=c[j]
            for h in range(m):
                sum[h]+=a[j][h]
    if min(sum)>=x:ans=min(ans,s)
print(ans) if ans!=12*10**5+1 else print(-1)

Submission status: Accepted

Solution code:
from functools import reduce

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

mincost = 10**8

for i in range(2**n):
	case = [0] * (m+1)
	for j in range(n):
		if (i >> j) & 1:
			case = list(map(sum, zip(case, lb[j])))
	
	if reduce(lambda u, v: u and v, list(map(lambda y: y >= x, case[1:]))):
		mincost = min(mincost, case[0])

if mincost < 10**8:
	print(mincost)
else:
	print(-1)

Submission status: Accepted

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

skill = [0] + [0] * m
ans = float("inf")
for i in range(2**n):
    i = format(i,"0{}b".format(n))
    for j in range(n):
        if str(i)[j] =="1":
            for l in range(m+1):
                skill[l] += list[j][l]
    money = skill.pop(0)
    if all(i>=x for i in skill):
        if ans>money:
            ans = money
    skill = [0] + [0] * m
if ans ==float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
def ip():return list(map(int,input().split()))

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

ans=12*10**5+1
for i in range(1,2**n):
    f=bin(i)[2:]
    sum=[0]*m
    while len(f)<n:f='0'+f
    s=0
    for j in range(n):
        if f[j]=='1':
            s+=c[j]
            for h in range(m):
                sum[h]+=a[j][h]
    F=True
    for h in range(m):
        if sum[h]<x:F=False
    if F==True:ans=min(ans,s)
print(ans) if ans!=12*10**5+1 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)]
c = [ca[i][0] for i in range(n)]
a = [ca[i][1:] for i in range(n)]
l = 0
ans = sum(c) 
for i in range(2 ** n):
    get = [0] * m
    kari = 0
    for j in range(n):
        if (i >> j) & 1: #i(ex.5)を2進数(ex.101)に一桁ずつ変換
            get = [x + y for (x, y) in zip(get, a[j])]
            kari += c[j]
    #print(get,kari)
    #print([k >= x for k in get])
    if all([k >= x for k in get]):
        ans = min(ans,kari)
        l += 1
if l == 0:
    ans = -1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m, x = map(int, input().split())
ca = [tuple(map(int, input().split()))for _ in range(n)]
INF = 10**18
ans = INF
proficiency = [0]*m


def dfs(i, cost):
    if i == n:
        global ans
        if cost < ans and all(x <= proficiency[j]for j in range(m)):
            ans = cost
        return 0
    c, *A = ca[i]
    for j in range(m):
        proficiency[j] += A[j]
    dfs(i+1, cost+c)
    for j in range(m):
        proficiency[j] -= A[j]

    dfs(i+1, cost)


dfs(0, 0)
print(ans if ans != INF else -1)

Submission status: Accepted

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

INF = 10**18

ans = INF
for a in range(1<<n):
    cost = 0
    d = [0 for i in range(m)]
    for b in range(n):
        if(a>>b&1):
            cost += c[b]
            for i in range(m):
                d[i] += k[b][i]
    ok = True
    for b in range(m):
        if (d[b] < x):
            ok = False
    if (ok):
        ans = min(ans, cost)
if (ans == INF):
    print (-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [tuple(map(int, input().split()))for _ in range(n)]
INF = 10**18
ans = INF
for bit in range(1 << n):
    cost = 0
    proficiency = [0]*m
    for i in range(n):
        if bit >> i & 1:
            c, *A = ca[i]
            cost += c
            for j in range(m):
                proficiency[j] += A[j]
    if cost < ans and all(x <= proficiency[j]for j in range(m)):
        ans = cost
print(ans if ans != INF else -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 bit in product((0, 1), repeat=n):
    proficiency = [0]*m
    cost = 0
    for i in range(n):
        if bit[i]:
            c, *A = ca[i]
            cost += c
            for j in range(m):
                proficiency[j] += A[j]
    if cost < ans and all(x <= proficiency[j] for j in range(m)):
        ans = cost
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
import sys
from itertools import product
input = sys.stdin.readline
N, M, X = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(N)]
res = -1
for p in product([0, 1], repeat=N):
    sum = [0] * M
    for i in range(N):
        if p[i]:
            for j in range(M):
                sum[j] += grid[i][j + 1]
    if all([sum[j] >= X for j in range(M)]):
        cost = 0
        for i in range(N):
            cost += p[i] * grid[i][0]
        if res == -1:
            res = cost
        else:
            res = min(res, cost)
    else:
        continue
print(res)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
for i in range(m):
  skill=0
  for j in range(n):
    skill+=l[j][i+1]
  if skill<x:
    print(-1)
    break
else:
  min_total=0
  for i in range(n):
    min_total+=l[i][0]
  for i in range(2**n):
    total=0
    s=[0]*m
    for j in range(n):
      if (i>>j)&1:
        total+=l[j][0]
        for k in range(m):
          s[k]+=l[j][k+1]
    if min(s)>=x:
      if min_total>=total:
        min_total=total
  print(min_total)

Submission status: Accepted

Solution code:
import itertools

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:])

L = [0, 1]
num = N
bits_list = list(itertools.product(L, repeat=num))

min_cost = float('inf')
for bits in bits_list:

    cost = 0
    understands = [0 for j in range(M)]
    for i in range(N):
        if bits[i] == 1:
            cost += C[i]
            for j in range(M):
                understands[j] += A[i][j]
    
    clear = True
    for u in understands:
        if u < X:
            clear = False
            break
    
    if clear and cost < min_cost:
        min_cost = cost

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

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,M,X = MI()
L = LI2(N)
ans = INF
for l in product([0,1],repeat=N):
    know = [0]*M
    cost = 0
    for i in range(N):
        if l[i]==1:
            cost += L[i][0]
            for j in range(M):
                know[j] += L[i][j+1]
    if min(know)<X:
        continue
    ans = min(ans,cost)
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
choices = []
for i in range(2 ** n):
    tmp = []
    for j in range(n):
        if ((i >> j) & 1):
            tmp.append(j)
    choices.append(tmp)
#choices.sort()
#del choices[0]
books = [ list(map(int,input().split())) for _ in range(n)]
anscost = float('inf')
for choice in choices:#[0, 1]
    cost = 0
    learn = [ 0 for _ in range(m)]
    for i in choice:
        book = books[i]
        cost += book[0]
        for j in range(1,m+1):
            learn[j-1] += book[j]
    #print("-----")
    #print(choice)
    #print(learn)
    if min(learn) >= x:
        anscost = min(anscost,cost)
if anscost ==  float('inf'):
    print(-1)
else:
    print(anscost)

Submission status: Accepted

Solution code:
def __min_cost(idx, cost, studied, costs):
    if idx >= n:
        return
    __min_cost(idx+1, cost, studied, costs)
    cost += cs[idx]
    studied = [s+i for s, i in zip(studied, mat[idx])]
    if all(s >= x for s in studied):
        costs.add(cost)
    else:
        __min_cost(idx+1, cost, studied, costs)

def min_cost():
    costs = set()
    __min_cost(0, 0, [0]*m , costs)
    if len(costs) > 0:
        return min(costs)
    else:
        return -1

n, m, x = map(int, input().split())
mat = []
cs = []
for _ in range(n):
    data = list(map(int, input().split()))
    cs.append(data[0])
    mat.append(data[1:])
print(min_cost())

Submission status: Accepted

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

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

ans = 10 ** 21
for b in range(2 ** n):
  A = [0] * m
  c = 0
  for i in range(n):
    if (1 & (b >> i)):
      c += CA[i][0]
      for itr, a in enumerate(CA[i][1:]):
        A[itr] += a
  if all(a >= x for a in A):
    ans = min(ans, c)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
arr=[[0 for i in range(m+1)] for j in range(n)]
b=[0]*18
ans=-1
flag=1
for i in range(n):
    arr[i]=list(map(int,input().split()))
for i in range(2**n):
    b=[0]*18
    for j in range(n):
        flag=1
        if (1& i>>j):
            for s in range(m+1):
                b[s]= b[s]+arr[j][s]
        for y in range(1,m+1):
            if(b[y]<x):
                flag=0
                
        if flag :
            if ans==-1 or ans>b[0]:
                ans=b[0]
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int,input().split())
ca = [list(map(int,input().split())) for i in range(n)]
import itertools
import numpy as np
from collections import deque

ca = np.array(ca)
bit_all = list(itertools.product(range(2),repeat=n))
ans = deque()

for bit in bit_all:
    bit = bit*(m+1)
    bit = np.array(bit).reshape([m+1,n]).T
    buy =  ca * bit
    buy = list(np.sum(buy,axis=0))
    if min(buy[1:]) >= x:
        ans.append(buy[0])

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

Submission status: Accepted

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

min_cost = 1200001
for i in range(2**n):
    cost = 0
    skill = [0 for _ in range(m)]
    for j in range(n):
        if (i>>j) &1 == 1:
            cost += book[j][0]
            for k in range(m):
                skill[k] += book[j][k+1]
    if min(skill) >= x:
        min_cost = min(min_cost, cost)

print('-1' if min_cost == 1200001 else min_cost)

Submission status: Accepted

Solution code:
#ABC167-C
import itertools
flg = True
n,m,x = map(int,input().split())
algo = []
tmp = []
for _ in range(n):
    algo.append(list(map(int,input().split())))
    
book = list(itertools.product([0,1],repeat=n))
abi = [0 for _ in range(m)]

for pattern in book:
    #値の初期化
    abi = [0 for _ in range(m)]
    money = 0
    flg = True
    
    for i in range(len(pattern)):
        for j in range(m):
            abi[j] += algo[i][j+1] * pattern[i]
        money += algo[i][0] * pattern[i]
        
    abi_min = [p for p in abi if p < x]
        
    if len(abi_min) != 0:
        flg = False
    if flg:
        tmp.append(money)

if len(tmp) > 0:
    print(min(tmp))
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
A = [[] for _ in range(n)]
c = [0]*n

for i in range(n):
    c_as = list(map(int, input().split()))
    c[i], A[i] = c_as[0], c_as[1:]

INF = 10**9
ans = INF

for s in range(0, 1 << n):
    smart = [0] * m
    cost_sum = 0
    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]

    judge = True
    for j in range(m):
        if smart[j] < k:
            judge = False

    if judge:
        ans = min(ans, cost_sum)

if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
def __min_cost(idx, cost, studied, costs):
    if idx >= n:
        return
    __min_cost(idx+1, cost, studied, costs)
    cost += cs[idx]
    studied = [s+i for s, i in zip(studied, mat[idx])]
    if all(s >= x for s in studied):
        costs.add(cost)
    __min_cost(idx+1, cost, studied, costs)

def min_cost():
    costs = set()
    __min_cost(0, 0, [0]*m , costs)
    if len(costs) > 0:
        return min(costs)
    else:
        return -1

n, m, x = map(int, input().split())
mat = []
cs = []
for _ in range(n):
    data = list(map(int, input().split()))
    cs.append(data[0])
    mat.append(data[1:])
print(min_cost())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
import numpy as np

def main():  
    N,M,X = map(int,input().split())
    book = np.array([input().split() for _ in range(N)],np.int32)
    ans = INF
    for bit in range(1<<N):
        ret = np.zeros(M + 1,np.int32)
        for i in range(N):
            if (bit>>i)&1:
                ret += book[i]
        if np.all(ret[1:] >= X):
            ans = min(ans,ret[0])
    print(ans if ans < INF else -1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import numpy as np
N, M, X = map(int, input().split())
data = np.array([list(map(int, input().split())) for i in range(N)], dtype=np.int64)

prices = data[:, 0]
effects = data[:, 1:]
 
ans_cands = []
# 2**N通りをchecl
for i in range(2 ** N):
    cur_costs = []
    cur_effects = np.zeros(M)
    # 現在の組み合わせでどの本を買ってるのかをcheck
    for j in range(N):
        if (i >> j) & 1:
            cur_costs.append(prices[j])
            cur_effects += effects[j, :]

    if np.all(cur_effects >= X):
        ans_cands.append(sum(cur_costs))

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

Submission status: Accepted

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

ans = INF
for i in range(1 << n):
    sm = [0] * m
    cost = 0
    for j in range(n):
        if i >> j & 1:
            cost += ca[j][0]
            for k, e in enumerate(ca[j][1:]):
                sm[k] += e

    if min(sm) >= x:
        ans = min(ans, cost)

if ans == INF:
    ans = -1

print(ans)