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())
books = list()
for i in range(N):
    books.append(list(map(int,input().split())))

lis = ["0"*(N-len(format(i,"b")))+format(i,"b") for i in range(1,2**N)]

minimam = 10**9
##pattern
for i in lis:
    tmp = [0] *(M+1)
    flag = 0
    ##adds
    for j in range(len(i)):
        if i[j] == "1":
            for k in range(M+1):
                tmp[k] += books[j][k]
    for k in range(1,M+1):
        if tmp[k] < X:
            flag = 1
            break
    if flag == 0:
        minimam = min(minimam,tmp[0])

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

Submission status: Accepted

Solution code:
import numpy as np
import itertools

n, m, x = map(int, input().split())
table = [[0 for i in range(m+1)] for j in  range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(m+1):
        table[i][j] = tmp[j]
        
table = np.array(table)

ans = float('inf')
for i in range(1, n+1):
    choices = list(itertools.combinations(range(n), i))
    for choice in choices:
        score = np.array([0 for i in range(m+1)])
        for c in choice:
            score += table[c]
        if all(score[1:] >= x):
            ans = min(ans, score[0])
            
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple

MAX = 13 * pow(10, 5)


def solve(
    prices: List[int], values: List[List[int]], target: int, rows: int, cols: int
) -> Optional[int]:
    min_price = MAX
    for i in range(rows):
        for picked in itertools.combinations(range(rows), i + 1):
            for j in range(cols):
                if sum(values[k][j] for k in picked) < target:
                    break
            # for else
            else:
                min_price = min(min_price, sum(prices[k] for k in picked))
    return min_price if min_price < MAX else None
    # dp[i] = (p, l) min price p to get to level l (max target)
    dp = [[(0, 0)] * cols for _ in rows]
    for i in range(rows):
        pi = prices[i]
        vi = values[i]
        dp = []
        for j in range(cols):
            if l < target:
                dp.append((pi + p, l + vi[j]))
    return target


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N, M, X = map(int, input().split())
    values = []
    prices = []
    for _ in range(N):
        p, *v = map(int, input().split())
        assert len(v) == M
        prices.append(p)
        values.append(v)
    result = solve(prices, values, X, N, M)
    print(result if result else -1)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m,x = map(int,input().split())
c = []
a = []
ans = 10**9
check = False
for _ in range(n):
  dc,*da = map(int,input().split())
  c.append(dc)
  a.append(da)
for i in range(1,1<<n):
  study = [0]*m
  total = 0
  for j in range(n):
    if (i>>j)%2:
      total += c[j]
      for k in range(m):
        study[k] += a[j][k]
  if all([l>=x for l in study]):
    check = True
    ans = min(ans,total)
if check:
  print(ans)
else:
  print(-1)

Submission status: Accepted

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

ans = []
for i in range(2**n):
  pat = [0] * n
  r = [0] * m
  money = 0
  for j in range(n):
    if ((i>>j)&1):
      pat[n-1-j] = 1
  for x in range(len(pat)):
    if pat[x] == 1:
      money += a[x][0]
      for y in range(m):
        r[y] += a[x][y+1]
  flag = True
  for z in range(m):
    if r[z] < X: 
      flag = False
      break
  if flag: 
    ans.append(money)
print(min(ans) if ans else -1)

Submission status: Accepted

Solution code:
def main():
    n ,m, x = map(int, input().split())
    c, a = [0 for i in range(n)], [[0 for i in range(m)] for j in range(n)]
    for i in range(n):
        c[i], *a[i] = [int(i) for i in input().split()]
    ans = solve(n, m, x, c, a)
    print(ans)


def solve(n, m, x, c, a):
    INF = 10 ** 9
    ans = INF
    for bits in range(2 ** n):
        cost, skill = 0, [0 for i in range(m)]
        #print(f'{bits=}')
        for i in range(n):
            bit = bits >> i & 1
            #print(f'{bit=}')
            if bit:
                cost += c[i]
                for j in range(m):
                    skill[j] += a[i][j]
        #print(skill)
        if judge(skill, x):
            ans = min(ans, cost)
    return -1 if ans == INF else ans

def judge(skill, x):
    for i in skill:
        if i < x:
            return False
    return True

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n, m, x = map(int, input().split())
temp = [list(map(int, input().split())) for _ in range(n)]
ans = []
for li in itertools.product([0,1], repeat=n):
    cnt = 0
    check = np.zeros(m, np.int)
    for i in range(n):
        if li[i] == 1:
            check += np.array(temp[i][1:])
            cnt += temp[i][0]
    if min(check) >= x:
        ans.append(cnt)
print(min(ans) if len(ans) !=0 else -1)

Submission status: Accepted

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

ans = 10 ** 7
for i in range(2 ** n):
    TCA = [0 for i in range(m + 1)]
    f = 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            TCA = [x + y for (x, y) in zip(TCA, CA[j])]
        else:
            pass
    for j in range(1, m + 1):
        if TCA[j] < x:
            f = 1
            break
        else:
            pass
    if f == 0:
        ans = min(ans, TCA[0])
    else:
        pass
if ans == 10 ** 7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
c=[ca[i][0] for i in range(n)]
a=np.array([ca[i][1:] for i in range(n)])

#たっせいできるか
ans=10**9
if min(np.sum(a, axis=0))<x:
  print(-1)
  sys.exit()
for i in range(2**n):
  l=list(bin(i)[2:].zfill(n))
  #print(l)
  a_sum=np.array([0]*m)
  cost=0
  for j in range(n):
    if l[j]=='1':
      a_sum+=a[j]
      cost+=c[j]
  #print(a_sum)
  if min(a_sum)>=x:
    ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    m = kwargs["m"]
    x = kwargs["x"]
    C = kwargs["C"]
    A = kwargs["A"]
    res = -1

    for i in range(2 ** n):
        l = [j for j in '{0:0{1}b}'.format(i, n)]
        scores = [0 for i in range(m)]
        price = 0

        for j in range(n):
            if l[j] == '1':
                for k in range(m):
                    scores[k] += A[j][k]

                price += C[j]

        if min(scores) >= x:
            if res == -1:
                res = price

            res = min(res, price)

    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"], kwargs["m"], kwargs["x"] = [int(i) for i in cin]

    kwargs["C"] = []
    kwargs["A"] = []
    for i in range(kwargs["n"]):
        cin = input().split()
        c = [int(i) for i in cin][0]
        a = [int(i) for i in cin][1:]
        kwargs["C"].append(c)
        kwargs["A"].append(a)

    cout = main(kwargs)
    print(cout)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m,x=mii()
chk=False
ansmoney=10**100
c=[]
arr=[]

for i in range(n):
    mat=limii()
    c.append(mat[0])
    arr.append(mat[1:])

for i in product([0,1],repeat=n):
    total=0
    chkarr=[0]*m
    for j in range(n):
        if i[j]==1:
            total+=c[j]
            for k in range(m):
                chkarr[k]+=arr[j][k]
            
    
    cnt=0
    for p in range(m):
        if chkarr[p]>=x:
            cnt+=1
    if cnt==m:
        chk=True
        ansmoney=min(ansmoney,total)
if chk:
    print(ansmoney)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools

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

ans = (10 ** 5) * 12 + 1

for choose in itertools.product([0,1], repeat=N):
    cnt_ca = 0
    ability = [0] * M
    money = 0
    for c in choose:
        if c == 1:
            money += CA[cnt_ca][0]
            for i in range(M):
                ability[i] += CA[cnt_ca][i+1]
        cnt_ca += 1
    if min(ability) >= X:
        ans = min(ans,money)

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

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

N, M, X = map(int, input().split())
C = [None]*N
A = [None]*N
for i in range(N):
    line = list(map(int, input().split()))
    C[i] = line[0]
    A[i] = np.array(line[1:])

choose = [True, False]

min_price = -1

for books in product(choose, repeat=N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if books[i]:
            knowledge += A[i]
            price += C[i]
    if np.any(knowledge < X):
        continue
    if min_price == -1:
        min_price = price
    min_price = min(min_price, price)

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

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

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

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

ans = np.inf

for i in range(2**N):
    point = np.zeros(M)
    cost = 0

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

    if np.all(point >= X):
        ans = min(ans, cost)

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

Submission status: Accepted

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

books=[]

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

cost = 10**18
for i in range(2**n):

    i = format(i,'0{}b'.format(n))

    flg =0
    total =0
    skill=[0]*m
    for j in range(n):
        if i[j]=='1':
            book_j = books[j]
            
            total += book_j[0]

            for l in range(len(book_j)):
                if l==0:
                    continue
                else:
                    skill[l-1]+=book_j[l]

    for k in range(m):
        if skill[k]<x:
            flg+=1
    
    if flg==0:
        cost = min(cost,total)

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

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
book = [list(map(int,input().split()))for _ in range(n)]
ans = float("inf")


for i in range(1,n+1):
    for k in itertools.combinations(range(n),i):
        tmp = 0
        exp = [0]*m
        for j in k:
            gold = False
            for i,a in enumerate(book[j]):
                if i==0:
                    tmp += a
                else:
                    exp[i-1] += a
        if min(exp) >= x:
            ans = min(ans,tmp)

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

Submission status: Accepted

Solution code:
from itertools import combinations

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

minn = float('inf')
idx = [i for i in range(n)]
for i in range(1, n + 1):
    for comb in combinations(idx, i):
        status = [0] * m
        money = 0
        for j in comb:
            money += ca[j][0]
            for i, ai in enumerate(ca[j][1:]):
                status[i] += ai
        if min(status) >= x:
            minn = min(minn, money)
print(-1 if minn > 10**9 else minn)

Submission status: Accepted

Solution code:
def is_valid(vals, M, X):
    for i in range(M):
        if vals[i] < X:
            return False
    return True

def solve(N, M, X, C, A):
    ret = float("inf")
    for i in range(2 ** N):
        tmp_vals = [0 for _ in range(M)]
        cost = 0
        for j in range(N):
            if (i >> j) & 1:
                cost += C[j]
                for k in range(M):
                   tmp_vals[k] += A[j][k]
        ret = min(ret, cost) if is_valid(tmp_vals, M, X) else ret
    return ret if ret != float("inf") else -1




if __name__ == '__main__':
    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:])

    print(solve(N, M, X, C, A))

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int, input().split())
argo = list()
for i in range(n):
    argo.append(list(map(int, input().split())))
least = float("inf")
test = [x] * m
for i in range(1,n+1):
    tmp = list(itertools.combinations(argo, i))
    for j in range(len(tmp)):
        boolean = True
        money = 0
        check = [0] * m
        for k in range(i):
            money += tmp[j][k][0]
            for l in range(m):
                check[l] += tmp[j][k][l+1]
        for k in range(m):
            if check[k] < x:
                boolean = False
                break
        if boolean:
            if money <= least:
                least = money
if least == float("inf"):
    print(-1)
else:
    print(least)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
C = [0]*N
A = [[0] for _ in range(N)]
for i in range(N):
    tmp = list(map(int,input().split()))
    C[i] = tmp[0]
    A[i] = tmp[1:M+1]
f = False
money_min = 100000000000
for i in range(1,2**N):
    use = format(i,"0{}b".format(N))
    money = 0
    understand = [0]*M
    for j in range(N):
        if use[j] == "1":
            money += C[j]
            for k in range(M):
                understand[k] += A[j][k]
    if min(understand) >= X and money < money_min:
        money_min = money
        f = True

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

Submission status: Accepted

Solution code:
# N = int(input())

import numpy as np

N,M,X = list(map(int, input().split()))
prices = []
As = np.zeros((N,M+1), dtype=int)

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

queue = []

def f(id, price, skill):
    # print(skill.min())
    
    if skill.min()>=X:
        # print("here")
        return price
    else:
        if id >= N:
            return np.inf
        else:
            return min(f(id+1, price+As[id,0], skill + As[id, 1:]), f(id+1, price, skill))

ans = f(0,0,np.zeros(M))
if ans == np.inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
def resolve():
    n, m, x = map(int, input().split())
    books = np.array([list(map(int, input().split())) for _ in range(n)])

    ans = 10 ** 7
    for i in range(2 ** 12):
        money = 0
        skills = np.zeros(m)
        for j in range(n):
            if ((i >> j) & 1):
                money += books[j][0]
                skills += books[j][1:]
        if (skills >= x).all():
            ans = min(ans, money)

    if ans == 10 ** 7:
        print(-1)
        return
    print(ans)
    
resolve()

Submission status: Accepted

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


ans = float("inf")
for p in itertools.product([0,1],repeat = N):
    cost = 0
    algo = [0]*M
    for i in range(N):
        if p[i]:
            cost += CAs[i][0]
            for j in range(M):
                algo[j] += CAs[i][j+1]
    for a in algo:
        if a < X:
            break
    else:
        ans = min(ans,cost)

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

Submission status: Accepted

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

costs = []
arrays = []
for _ in range(N):
    arr = tuple(map(int, input().split()))
    costs.append(arr[0])
    arrays.append(arr[1:])

total_costs = []
for i in range(1, 2**N):
    total_cost = 0
    selected_arrays = [] 
    for j in range(0, N):
        if (i >> j)&1:
            total_cost += costs[j]
            selected_arrays.append(arrays[j])
            
    rikais = [0] * M
    for arr in selected_arrays:
        for i, a in enumerate(arr):
            rikais[i] += a

    if all(map(lambda r: r>=X, rikais)):
        total_costs.append(total_cost)

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

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np


def main():
    n, m, x = list(map(int, input().split()))
    A = np.array([list(map(int, input().split())) for _ in range(n)])
    cost = []
    for i in range(n):
        combs = combinations(range(n), i+1)
        for comb in combs:
            A2 = np.array([A[c] for c in comb])
            A2sum = np.sum(A2, axis=0)
            if (A2sum[1:] >= x).all():
                cost.append(A2sum[0])

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




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

lst = []

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


min_num = float("inf")
for i in range(N):
    a = itertools.combinations([i for i in range(N)], i+1)

    for j in a:
        tmp = [0 for _ in range(M)]
        for k in j:
            for r in range(M):
                tmp[r] += lst[k][r+1]
        for t in tmp:
            if t < X:
                break
        else:
            cnt = 0
            for c in j:
                cnt += lst[c][0]
            if cnt <= min_num:
                min_num = cnt

if min_num == float("inf"):
    print(-1)
else:
    print(min_num)

Submission status: Accepted

Solution code:
import itertools as itt
def resolve():
    N,M,X = map(int,input().split())
    CA = [list(map(int,input().split())) for i in range(N)]
    mxc = float('inf')
    for r in range(N+1):
        for cmb in itt.combinations(CA,r):
            cost = 0
            tbl = [0]*M
            for x in cmb:
                cost+=x[0]
                for i in range(M):
                    tbl[i]+= x[i+1]

            for i in tbl:
                if i < X:
                    break
            else:
                mxc = min(cost,mxc)
                
    if mxc == float('inf'):
        print(-1)
    else:
        print(mxc)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = float('inf')
for i in range(1, n+1):
    for c_books in combinations(books, i):
        scores = [0] * m
        price = 0
        for book in c_books:
            price += book[0]
            for j in range(m):
                scores[j] += book[j+1]
        if all([scores[k] >= x for k in range(m)]):
            ans = min(ans, price)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

C = [1 for i in range(N)]
A = [[0 for i in range(M)] for j in range(N)]

for i in range(N):
    input_ = list(map(int, input().split()))

    C[i], A[i] = input_[0], input_[1:]

price_min = 10 ** 9
for pattern in range(2 ** N):
    price_sum = 0
    skill_levs = [0 for i in range(N)]

    pattern = str(bin(pattern)).lstrip('0b').zfill(N)

    for idx, p in enumerate(pattern):
        if p == '1':
            price_sum += C[idx]
            skill_levs = [lev + up for lev, up in zip(A[idx], skill_levs)]
    if min(skill_levs) >= X:
        price_min = min(price_min, price_sum)

if price_min != 10 ** 9:
    print(price_min)
else:
    print('-1')

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = map(int, input().split())
a = []
cost_lst = []
for _ in range(n):
    lst = (list(map(int, input().split())))
    cost_lst.append(lst.pop(0))
    a.append(lst)
data = np.array(a)

min_cost = 9999999999

for i in range(2 ** n):
    b = np.zeros(m)
    cost = 0
    num = i
    for j in range(n):
        if num % 2 == 0:
            b += data[j]
            cost += cost_lst[j]
        num = num // 2
    for skill in b:
        if skill < x:
            break
    else:
        min_cost = min(min_cost, cost)

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

Submission status: Accepted

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

l = []

def f(cs, i, a):
    for j in range(n - i - 1):
        cs2 = cs + caas[i + j + 1][0]
        a2 = [y + a[k] for k, y in enumerate(caas[i + j + 1][1:])]
        if min(a2) >= x:
            l.append(cs2)
        else:
            f(cs2, i + j + 1, a2)

f(0, -1, [0 for _ in range(m)])

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

Submission status: Accepted

Solution code:
from itertools import combinations

import numpy as np


def run():
    n, m, x = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(n)]
    c = np.array([d[0] for d in data])
    a = np.array([d[1:] for d in data])

    candidates = []
    for buy_num in range(1, n + 1):
        for comb in combinations(range(n), buy_num):
            temp_a = a[comb, :]

            sum_a = np.sum(temp_a, axis=0)

            if np.all(sum_a >= x):
                sum_c = np.sum(c[list(comb)])
                candidates.append(sum_c)

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


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

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

ans = INF
for s in (range(1 << N)):
    A = defaultdict(int)
    cost = 0
    for i in range(N):
        if s >> i & 1:
            book = books[i]
            cost += book[0]
            for i in range(1, M + 1):
                A[i] += book[i]
    ok = True
    for i in range(1, M + 1):
        if A[i] < X:
            ok = False
            break
    if ok:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import sys

N, M, X = map(int, sys.stdin.readline().strip().split())

C = []
A = []
for _ in range(N):
    c, *a = map(int, sys.stdin.readline().strip().split())
    C.append(c)
    A.append(a)

ans = float('inf')

for i in range(2 ** N):
    bit = [(i >> j) & 1 for j in range(N)]  # 本を購入するかしないか

    understand = [0] * M
    for i, b in enumerate(bit):
        if b != 0:
            # print(f'i: {i}, lenA: {len(A)}, len under: {len(understand)}')
            understand = [x + y for x, y in zip(A[i], understand)]

    if min(understand) >= X:
        cost = [c * b for c, b in zip(C, bit)]
        ans = min(sum(cost), ans)

if ans == float('inf'):
    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):
    A = list(map(int,input().split()))
    c[i] = A[0]
    a[i] = A[1:]

t = [0] * m
for i in range(n):
    for j in range(m):
        t[j] += a[i][j]
if(min(t) < x):
    print(-1)
    exit()
mi = sum(c) + 1
for i in range(2**n):
    cost = 0
    sk = [0] * m
    for j in range(n):
        y = 2**j
        if(i & y != 0):
            cost += c[j]
            for k in range(m):
                sk[k] += a[j][k]
    if(min(sk) >= x):
        mi = min(mi,cost)
print(mi)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]
res = n*(10**5)+1
for i in range(2**n-1):
    s = format(i+1, '0'+str(n)+'b')
    und = [0]*m
    mon = 0
    for j in range(n):
        if s[j] == '0':
            continue
        else:
            for c in range(m):
                und[c] += ca[j][c+1]
            mon += ca[j][0]
    if min(und) >= x:
        res = mon if mon < res else res
if res == n*(10**5)+1:
    res = -1
print(res)

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()))
	#a = s.pop(0)
	#c.append(a)
	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:
import numpy as np

N, M, X = map(int, input().split())
CA = []
for _ in range(N):
    Ci, *A = map(int, input().split())
    CA.append((Ci, A))

ans = 10**8
studied = np.array([0] * M)

for i in range(2**N):
    flag = True
    tmp_ans = 0
    studied = np.array([0] * M)
    for j in range(N):
        if i >> j & 1:
            tmp_ans += CA[j][0]
            studied += CA[j][1]
    for study in studied:
        if study < X:
            flag = False
            break
    if flag:
        ans = min(ans, tmp_ans)

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N, M, X = map(int, input().split())
costs = []
effects = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    costs.append(tmp[0])
    effects.append(tmp[1:])

ans = INF
for i in range(1<<N):
    total_costs = 0
    algo = [0] * M
    for k in range(N):
        if 1&i>>k:
            total_costs += costs[k]
            for j, effect in enumerate(effects[k]):
                algo[j] += effect
    is_ok = True
    for a in algo:
        if a < X:
            is_ok = False
            break
    if is_ok:
        ans = min(ans, total_costs)

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