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 permutations


def resolve():
    n, m, x = map(int, input().split())
    inf = float('INF')
    data = [list(map(int, input().split())) for i in range(n)]

    if n > 6:
        d = get(data[:n//2], n//2, m)
        e = get(data[n//2:], n - n//2, m)
        d = merge(d,e,m)
    else:
        d = get(data, n, m)

    ans = inf
    for tt,cost in d.items():
        for t in tt:
            if x > t:
                break
        else:
            if ans > cost:
                ans = cost

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

def get(data, n, m):
    d = {}
    for b in range(1 << n):
        tmp = [0 for i in range(m)]
        cost = 0
        for i in range(n):
            if ((1<<i) & b) == 0:
                continue
            cost += data[i][0]
            for j in range(1,m+1):
                tmp[j-1] += data[i][j]
        tt = tuple(tmp)
        if tt not in d:
            d[tt] = cost
        else:
            if cost < d[tt]:
                d[tt] = cost
    return d

def merge(d,e,m):
    f = {}
    for k,v in d.items():
        for s,t in e.items():
            tt = tuple(k[i]+s[i] for i in range(m))
            cost = v + t
            if tt not in f:
                f[tt] = cost
            else:
                if cost < f[tt]:
                    f[tt] = cost
    return f

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import numpy as np

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

for i in range(N):
    Ctmp,*Atmp=map(int, input().split())
    C.append(Ctmp)
    A.append(np.array(Atmp))

sum = 0

arr=[]
tmpC=[]
tmpA=[]

for bit in range(1<<N): # 0(0b000)から7(0b111)まで
    tmpmon=0
    tmpX=np.array([0]*M)
    for i in range(N):
        mask = 1 << i
        if bit&mask: # 右からi番目にビットが立っているかどうか判定
            tmpmon+=C[i]
            tmpX+=A[i]
    tmpC.append(tmpmon)
    tmpA.append(tmpX)


ans = 9999999999
for i in range(len(tmpC)):
    if np.amin(tmpA[i]) >= X:
        if ans > tmpC[i]:
            ans=tmpC[i]

if ans == 9999999999:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import itertools
# 学びたい数: M
# 理解度初期値: 0
# 参考書数: N
# ゴール: 全理解度をX以上。最小購入金額

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

# 参考書の定義
sankousyo = []
rikaido = [0]*M

for i in range(N):
    sankousyo.append(list(map(int, input().split())))

# 購入する参考書の価格
minBag = 10**9

# bit全探索
n = len(sankousyo)
for i in range(2 ** n):
    bag = []
    rikaido = [0]*M
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(sankousyo[j][0])  # フラグが立っていたら bag に参考書を詰める
            # 全て理解度を超えているかチェック
            flg = True
            for m in range(M):
                rikaido[m] += sankousyo[j][m+1]
                if rikaido[m] < X:
                    flg = False
            if flg == True and minBag > sum(bag):
                minBag = sum(bag)
    #print(bag, rikaido)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ls = []
for i in range(n):
    ca = list(map(int,input().split()))
    ls.append(ca)
    
pattern = [bin(i)[2:].zfill(n) for i in range(2**n)]

ans = 10000000
for i in ls:
    tmp = []
    for j in pattern:
        p2 = 0
        al = [0]*m
        for k in range(len(j)):#101
            if j[k] == "1":
                al = [x + y for (x, y) in zip(ls[k][1:], al)]
                p2 += ls[k][0]
        p = 0
        for k in al:
            if k < x:
                p += 1
                break
        if sum(al) < m*x:
          p += 1
        if p == 0:
            #print(p2)
            ans = min(ans,p2)
if ans == 10000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
Book = []
for i in range(N):
  Book.append(list(map(int,input().split())))
Cost = 10**15
for i in range(2**N):
  cost = 0
  A = [0 for i in range(M)]
  num = []
  j = 0
  while i > 0:
    if i%2 == 1:
      num.append(j)
    i = i//2
    j += 1
  for k in num:
    A = [x+y for (x,y) in zip(A,Book[k][1:])]
    cost += Book[k][0]
  if min(A) >= X:
    if cost < Cost:
      Cost = cost
if Cost == 10**15:
  print(-1)
else:
  print(Cost)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
data = []
for _ in range(N):
    data.append(list(map(int,input().split())))
cost = float("inf")
for i in range(2**N):
    temp = [0] * (M+1)
    for j in range(N):
        if ((i>>j)&1):
            for x in range(M+1):
                temp[x] += data[j][x]
    count = 0
    for f in temp[1:]:
        if f < X:
            break
        count += 1
    if count == M:
        cost = min([cost,temp[0]])
if cost == float("inf"):
    print(-1)
else:
    print(cost)

Submission status: Accepted

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

books = [[int(i) for i in input().split()] for j in range(n)]

def check(lst):
    return all([i >= x for i in lst])

ans = float("inf")
for k in range(1<<n):
    lst = [sum([(books[i][sub+1] if (k & 1<<i != 0) else 0) for i in range(n)]) for sub in range(m)]
    if check(lst):
        ans = min(ans, sum([(books[i][0] if (k & 1<<i != 0) else 0) for i in range(n)]))

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

Submission status: Accepted

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

import itertools


def main():
    n, m, x = map(int, input().split())
    ca_list = []
    for _ in range(n):
        ca_list.append(list(map(int, input().split())))

    min_c = 10 ** 20
    for i in range(2 ** n):
        cur_c = 0
        a_list = [0] * m
        for j in range(n):
            is_use = i & (2 ** j)
            if is_use:
                cur_c += ca_list[j][0]
                a_list = [a_list[k] + ca_list[j][k + 1] for k in range(m)]
        if all(k >= x for k in a_list) and cur_c < min_c:
            min_c = cur_c
    print(min_c if min_c != 10 ** 20 else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import numpy as np
skill = np.array([0 for i in range(m + 1)])
ans_buf = []

for i in range(1, 2 ** n):
    flag = True
    two = str(bin(i))
    two = two[2:].zfill(n)

    for j in range(n):
        if two[j] == '1':
            skill += np.array(buf[j])
    
    for j in range(m):
        if skill[j + 1] < x:
            flag = False
    if flag:
        ans_buf.append(skill)
    skill = np.array([0 for i in range(m + 1)])


ans = [i[0] for i in ans_buf]
if ans == []:
    ans = [-1]
ans = min(ans)
print(ans)

Submission status: Accepted

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc167/abc167_c
import sys
import itertools

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M, X = i2nn()
    C = [None] * N
    A = [None] * N
    sum_C_min = 0
    sum_A = [0] * M
    for i in range(N):
        C[i], *A[i] = i2nn()
        sum_C_min += C[i]
        for j in range(M):
            sum_A[j] += A[i][j]
    for a in sum_A:
        if a < X:
            print(-1)
            return
    for n in range(N - 1, 0, -1):
        sum_C_prev = sum_C_min
        for v in itertools.combinations(range(N), n):
            sum_C, ok = func(N, M, X, C, A, v)
            if ok and sum_C < sum_C_min:
                sum_C_min = sum_C
        if sum_C_prev == sum_C_min:
            print(sum_C_min)
            return
    print(sum_C_min)
    return

def func(N, M, X, C, A, v):
    sum_A = [0] * M
    sum_C = 0
    for i in v:
        sum_C += C[i]
        for j in range(M):
            sum_A[j] += A[i][j]
    for a in sum_A:
        if a < X:
            return sum_C, False
    return sum_C, True
main()

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

from itertools import combinations as c
add = lambda x,y: [i+j for i,j in zip(x,y)]
n,m,x = mp()
cost,mat = {},{}
for i in range(1,n+1):
    xx = ip()
    cost[i] = xx[0]
    mat[i] = xx[1:]
ans = []
rows = [i for i in range(1,n+1)]
for i in range(1,n+1):
    for j in list(c(rows,i)):
        t = [0]*m
        for k in j:
            t = add(t,mat[k])
        if all(ii>=x for ii in t):
            ans.append(sum([cost[ii] for ii in j]))
if ans == []:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

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

import itertools

n, m, x = map(int, input().split())
_list = [list(map(int, input().split())) for _ in range(n)]
n_list = [i for i in range(n)]
all_list = []
a = [0]*(m+1)
ans = 100000000000000000000000

for i in range(n):
    for j in itertools.combinations(n_list, i+1):
        all_list.append(j)

for i in all_list:
    a = [0]*(m+1)
    for j in i:
        for k in range(m+1):
            a[k] += _list[j][k]
    if a[0] < ans:
        if all(x <= a[i] for i in range(1, m+1)):
            ans = a[0]

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

Submission status: Accepted

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

c = []
for i in range(n):
  c.append(list(map(int, input().split())))
  
max = 999999999999
ans = max  
  
for i in range(2 ** n):
  list=[0]*(m+1)
  
  for j in range(n):
    if ((i >> j) & 1):
      for k in range(m+1):
        list[k] += c[j][k]
#  print(list)          
  if min(list[1:]) >= x:
#    print('koe',list)
    ans = min(ans, list[0])

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

Submission status: Accepted

Solution code:
import itertools as iter
import math as m

def main():
    N, M, X = list(map(int, input().split()))
    C = []
    for _ in range(N):
        C.append(list(map(int, input().split())))
    result = []
    for i in range(1, N+1):
        for c in iter.combinations(C, i):
            cost = 0
            s = [0] * (M+1)
            for x in c:
                for j, y in enumerate(x):
                    s[j] += y
                cost += x[0]
            if check(s[1:], X):
                result.append(cost)
    if len(result) > 0:
        print(min(result))
    else:
        print(-1)
    pass

def check(s, X) -> bool:
    return all([a >= X for a in s])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import Counter
import itertools
import fractions
#import numpy as np
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################

N,M,X=MI()
CA=LLI(N)

mi=10000000000000
ans=0

for i in range(1,N+1):
    kumi = itertools.combinations(CA,i)
    for k in kumi:
        target=[0]*(M+1)
        su=0
       
        for x in k:
            target = [a + b for (a,b) in zip(x,target)]
            su+=x[0]
        flag=True   
        for j in range(1,len(target)):
            if X > target[j]:
                flag=False
                break
        if flag:    
            mi=min(mi,su)
            ans+=1
if ans ==0:
    print(-1)
else:
    print(mi)

Submission status: Accepted

Solution code:
from itertools import combinations as IC
N, M, X = map(int, input().split())
ans = 10 ** 100
L = [list(map(int, input().split())) for i in range(N)]
#print(L)
for i in range(1, N + 1):
  T = list(IC(list(range(N)), i))
  #print(T)
  for j in T:
    t = 0
    l = [0] * M
    for n in list(j):
      for k in range(M+1):
        if k == 0:
          #print(L[n][0])
          t += L[n][0]
        else:
          l[k-1] += L[n][k]
    if len([n for n in l if n >= X]) == M:
      #print(l, t)
      ans = min(ans, t)
print(-1 if ans == 10 ** 100 else ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
from functools import reduce
from operator import add

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

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

success = []


def get_sum_books(args):
    return reduce(add, args)


for i in range(1, N + 1):
    for c in combinations(books, i):
        res = get_sum_books(c)
        if min(res[1:]) >= X:
            success.append(res[0])

if success:
    print(min(success))
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import product as pd
from collections import defaultdict as dd
n, m, x = map(int, input().split())
price_dic = {}
#naiyo_dic[book][skill]
naiyo_dic = dd(lambda: dd(lambda: 0))
for i in range(1, n+1):
    A = list(map(int, input().split()))
    price_dic[i] = A[0]
    for j in range(1, m+1):
        naiyo_dic[i][j] = A[j]
#print(price_dic)
#print(naiyo_dic)

def price_and_can(pattern):
    skill = [0] * (m+1)
    skill[0] = 10**5 + 1
    price = 0
    can_do = False
    for i, is_read in enumerate(pattern):
        book_num = i + 1
        if is_read == 1:
            price += price_dic[book_num]
            for j in range(1, m+1):
                skill[j] += naiyo_dic[book_num][j]
    if min(skill) >= x:
        can_do = True
    #print(pattern, skill, min(skill), price, x, can_do)
    return price, can_do

prices = []
for pattern in pd([0, 1], repeat=n):
    val, can_do = price_and_can(list(pattern))
    if can_do:
        prices.append(val)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
t = []
ans = 0
for i in range(n):
    l = list(map(int, input().split()))
    t.append(l)
    ans += l[0]
maximum = ans + 10
ans = maximum
for i in range(1, 2**n):
    f = [c for c in format(i, f'0{n}b')]
    money = 0
    scores = [0]*m
    for l in [j for k, j in zip(f, t) if k == '1']:
        money += l[0]
        for j in range(1, m+1):
            scores[j-1] += l[j]
    if len(list(filter(lambda y: y >= x, scores))) == m:
        ans = min(ans, money)
print(ans if ans != maximum else -1)

Submission status: Accepted

Solution code:
N, M, X = 3, 3, 10
ARR = [
    [60, 2, 2, 4],
    [70, 8, 7, 9],
    [50, 2, 3, 9],
]

N, M, X = 3, 3, 10
ARR = [
    [100, 3, 1, 4],
    [100, 1, 5, 9],
    [100, 2, 6, 5]
]

N, M, X = 8, 5, 22
ARR = [
    [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],
]

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

for i in range(N):
    ARR.append(list(map(int, input().split())))


def calculate(n, m, x, arr):
    result = []
    for i in range(2 ** n):

        tmpValue = 0
        mrr = [0] * m
        krr = [False] * m
        for j in range(n):
            res = i >> j & 1
            if res == 1:
                tmpValue = tmpValue + arr[j][0]
                for mIndex in range(m):
                    mrr[mIndex] = mrr[mIndex] + arr[j][mIndex + 1]
                    if mrr[mIndex] >= x:
                        krr[mIndex] = True
        if sum(krr) == m:
            result.append(tmpValue)

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


calculate(N, M, X, ARR)

Submission status: Accepted

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

INF = 10**10


def main(input, print):
    n, m, x = map(int, input().split())
    table = [[] for _ in range(n)]
    for i in range(n):
        table[i] = list(map(int, input().split()))
    ans = INF
    for i in range(1, n+1):
        p = itertools.combinations(range(n), i)
        for pj in p:
            t = 0
            mt = [0] * m
            for k in range(len(pj)):
                t += table[pj[k]][0]
                for l in range(m):
                    mt[l] += table[pj[k]][l+1]
            is_ok = True
            for l in range(m):
                if mt[l] < x:
                    is_ok = False
            if is_ok:
                ans = min(ans, t)
    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
n, m, x = map(int,input().split())
hako = []#参考書、0=買わない、1=買う


def taka(y,z):
    global hako
    if len(z) == n:
        hako.append(z)
        return
    zz = z.copy()
    zz.append(y)
    for i in range(2):
        taka(i,zz)


for i in range(2):
    taka(i,[])

#print(hako)

sankousyo = []

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

takahasikunn = [0]*(m+1)

ans = 13*10**5

for i in hako:
    clear = 0
    for j in range(n):
        if i[j] == 1:
            for k in range(m+1):
                takahasikunn[k] += sankousyo[j][k]
    for l in range(1,m+1):
        if takahasikunn[l] >= x:
            clear += 1
    if clear == m:
        ans = min(ans,takahasikunn[0])
    #print(takahasikunn)
    takahasikunn = [0]*(m+1)

if ans == 13*10**5:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M, X = map(int, input().split())
prices = []
effects = []
for i in range(N):
    c, *a = map(int, input().split())
    prices.append(c)
    effects.append(list(a))
 
prices = np.array(prices)
effects = np.array(effects)
 
 
ans = float("inf")
 
pats = []
for i in range(2 ** N):
    pat = bin(i).replace("0b", "")
    pat = "0" * (N - len(pat)) + pat
    pat = list(map(int, list(pat)))
    pats.append(pat)
    
pats = np.array(pats)
total_price = np.dot(pats, prices)
total_effects = np.dot(pats, effects)
cond = ((total_effects >= X).sum(axis=1) == M)
 
final = total_price[cond == 1]
if len(final) > 0:
    ans = int(final.min())
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

a=[]

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

smin=1000000*n
d=1000000*n


for i in range(0,2**n):
    mo=0
    x2=[0 for i2 in range(0,m)]
    
    for j in range(0,n):
        if ((i>>j)&1)==1:
            mo+=a[j][0]
            for k in range(0,m):
                x2[k]+=a[j][k+1]

    if min(x2)>=x:
        if mo<smin:
            smin=mo
    

if smin==d:
    print(-1)

else:
    print(smin)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

#totallist=[[0]*M]*N
totallist=np.zeros((N,M+1))
for i in range(N):
    totallist[i]=list(map(int,input().split()))


lis=list(range(N))
result = []
print_value =float('inf')
total_test=np.zeros(M+1)
for n in range(1,len(lis)+1):
    for conb in itertools.combinations(lis, n):
        for i in conb:
            total_test=total_test+totallist[i]
            if(np.count_nonzero(total_test[1:]>=X)==M):
                if(print_value>=total_test[0]):
                    print_value=total_test[0]
        total_test=np.zeros(M+1)
if(print_value==float('inf')):
    print(-1)
else:
    print(int(print_value))

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(N)]
ans = 10**10
for i in range(2 ** N):
    total = 0
    point = [0 for _ in range(M)]
    for j in range(N):
        if ((i >> j) & 1):
            total += CA[j][0]
            for k in range(M):
                point[k] += CA[j][k+1]
    f = True
    for j in range(M):
        if point[j] < X:
            f = False
    if f:
        ans = min(ans, total)
if ans != 10 ** 10:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

books = list()
for _ in range(n):
    books.append(list(map(int, input().split())))


target = list()
result = -1

for i in range(2**n):
    score = [0] * m
    tmp = 0
    for j in range(n):
        bit = i >> (n-j-1) & 1
        if bit:
            score = [a + b for a, b in zip(score, books[j][1:])]
            tmp += books[j][0]

    if all([a >= x for a in score]):
        if result == -1:
            result = tmp
        else:
            result = min(result, tmp)

print(result)

Submission status: Accepted

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

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

min =10**10

for i in range(2**n):
    ii=i
    rikai=[0]*m
    kane=0
    for j in reversed(range(n)):#j冊目はかう？

        if ii//(2**j)==1:
            ii-=(2**j)
            for k, a in enumerate(A[j]):
                if k==0:
                    kane+=a
                else:
                    rikai[k-1]+=a

    #判定
    hantei=True
    for i in rikai:
        if i<x:
            hantei=False

    if hantei==True:
        if min > kane:
            min=kane

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
item = []
result=[]
for x in range(N):
    C = list(map(int,input().split()))
    item.append(C)
n = len(item)
for i in range(2**n):
    A = [0]*M
    total = 0
    xx = 0
    for j in range(n):
        if ((i >> j) & 1):
            for m in range(M):
                A[m]+=item[j][m+1]
            total += item[j][0]
    for mm in range(M):
        if A[mm]>=X:
            xx+=1
    if xx==M:
        result.append(total)
if result==[]:
    print(-1)
    exit()
else:
    print(min(result))

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,x = inpm()
    c = [list(map(int,input().split())) for _ in range(n)]
    ans = float('inf')
    for num in range(1,n+1):
        for e in combinations(range(n),num):
            cost = 0
            under = [0 for _ in range(m)]
            for f in e:
                cost += c[f][0]
                for i in range(m):
                    under[i] += c[f][i+1]
            if min(under) >= x:
                ans = min(ans,cost)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

books_num, alg_num, goal = map(int, input().split())
book = [[None]*(alg_num + 1) for _ in range(books_num)]

for i in range(books_num):
    book[i] = list(map(int, input().split()))
# print(book)

ans = float('inf')
seq = [i for i in range(books_num)]
flag = True
for i in range(books_num, 0, -1):
    if(not flag):
        break
    flag = False
    for seq_tmp in itertools.combinations(seq, i):
        skill = [0]*alg_num
        ans_tmp = 0
        for j in seq_tmp:
            for k in range(alg_num):
                skill[k] += book[j][k+1]
            ans_tmp += book[j][0]
            # print(skill, ans_tmp, ans, seq_tmp)
            for k in range(alg_num):
                if skill[k] < goal:
                    break
            else:
                ans = min(ans, ans_tmp)
                flag = True
print(ans if ans != float('inf') else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, x = map(int, input().split())
ca = [0] * n
ca_sum = [0] * (m+1)
for i in range(n):
    ca[i] = list(map(int, input().split()))
    for j in range(m+1):
        ca_sum[j] += ca[i][j]

ans = 10 ** 10
for i in range(2 ** n):
    tmp = 0
    tmp_ca_sum = ca_sum.copy()
    for j, v in enumerate(format(i, r'0{}b'.format(n))):
        if v == '0':
            continue
        for k in range(m+1):
            tmp_ca_sum[k] -= ca[j][k]
    flag = True
    for v2 in tmp_ca_sum[1:]:
        if v2 < x:
            flag = False
            break
    if flag:
        ans = min(ans, tmp_ca_sum[0])

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

Submission status: Accepted

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

flag = False
ans = 10**10
for i in range(2 ** n):
    ans_lst = [0] * (m + 1)
    for j in range(n):
        if (i >> j) & 1:
            tmp = lst[j]
            for k in range(m + 1):
                ans_lst[k] += tmp[k]
        if all(score >= x for score in ans_lst[1:]):
            ans = min(ans, ans_lst[0])
            break

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

Submission status: Accepted

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

pair = []

for c1 in range(2):
    for c2 in range(2):
        for c3 in range(2):
            for c4 in range(2):
                for c5 in range(2):
                    for c6 in range(2):
                        for c7 in range(2):
                            for c8 in range(2):
                                for c9 in range(2):
                                    for c10 in range(2):
                                        for c11 in range(2):
                                            for c12 in range(2):
                                                pair.append([c1, c2, c3, c4, c5,c6, c7, c8, c9, c10, c11,c12])


zenkingaku = []
for pattern in pair:
    rikaido = [0 for _ in range(m)]
    kingaku = 0
    _pattern = pattern[:n]
    for ca_i, p in enumerate(_pattern):
        if p == 1:
            kingaku += ca[ca_i][0]
            for ca_j in range(m):
                rikaido[ca_j] += ca[ca_i][ca_j+1] 

    for ca_j in range(m):
        if rikaido[ca_j] < x:
            kingaku = -1

    if kingaku == -1:
        continue

    zenkingaku.append(kingaku)

if not zenkingaku:
    zenkingaku = [-1]
print(min(zenkingaku))

Submission status: Accepted

Solution code:
n,m,x =  list(map(int,input().split()))
c = [[]for _ in range(n)]
for i in range(n):
    c[i] = list(map(int,input().split()))
ans = float('inf')
for i in range(1,2**n):#bit
    tmp = 0
    tmpl = [0 for _ in range(m)]

    for j in range(n):#bitごとにみる
        if((i>>j&1)):
            tmp += c[j][0]
            for k in range(1,m+1):
                tmpl[k-1] += c[j][k]
    ok = 0
    for l in range(m):
        if tmpl[l] >= x:
            ok += 1
    if ok >= m:
        ans = min([ans,tmp])

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

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    import itertools
    n,m,x = map(int,stdin.readline().rstrip().split())
    mat = []
    for _ in range(n):
        temp = list(map(int,stdin.readline().rstrip().split()))
        mat.append(temp)
    
    sum = []
    for i in range(n+1):
        for l in itertools.combinations(mat,i):
            temp = [0]*(m+1)
            for k in range(m+1):
                for j in l:
                    temp[k]+=j[k]
            sum.append(temp)
    
    sum.sort(key=lambda x: x[0])
    for l in sum:
        ans = -1
        flag = True
        for j in l[1:]:
            if j < x:
                flag = False
                break
        
        if flag:
            ans=l[0]
            break
    
    print(ans)
main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools as it

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

CA = []

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

CA = np.array(CA)

def choice(N):
    ch = []
    for k in range(1,N+1):
        ch.append(list(it.combinations(range(N),k)))
    return list(it.chain.from_iterable( ch ))

ch = choice(N)
ans = 10**10

for c in ch:
    und = np.array( list(map( lambda i : sum(CA[c,i]), range(1,M+1))) )
    cost = sum(CA[c,0])
    if set( und >= X) == {True} and cost < ans:
        ans = cost

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

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
arr = []
money = []
vector = 0
for i in range(n):
  row = list(map(int, input().split()))
  money.append(row[0])
  arr.append(row[1:])
  vector += 2 ** (n-i-1)

ans = float('inf')
for i in range(vector+1):
  j = n-1
  result = [0] * m
  spend = 0
  while i > 0:
    if i % 2:
      result = [x + y for (x, y) in zip(result, arr[j])]
      spend += money[j]
    i //= 2
    j -= 1
  if min(result) >= x:
    ans = min(ans, spend)

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