Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
N, M, X = map(int, input().split())
CA = [np.array(list(map(int, input().split()))) for _ in range(N)]

ans = None

for i in range(1, N+1):
    for comb_list in combinations(CA, i):
        comb_list = np.array(comb_list)
        sum_list = comb_list.sum(axis=0)
        if np.all(sum_list[1:] >= X):
            if not ans or (ans > sum_list[0]):
                ans = sum_list[0]
print(-1 if ans is None else ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
li_a = []
li_c = []
for _ in range(N):
    temp = list(map(int, input().split()))
    li_temp = []
    for i in range(len(temp)):
        if i == 0:
            li_c.append(temp[i])
        else:
            li_temp.append(temp[i])
    li_a.append(li_temp)
min_ = 10**15
for s in range(1<<N):
    money = 0
    dic = {}
    for i in range(M):
        dic[i] = 0
    for j in range(N):
        if (1<<j) & s:
            money += li_c[j]
            for k in range(len(li_a[j])):
                dic[k] += li_a[j][k]
    b = True
    for i in range(M):
        if dic[i] < X:
            b = False
            break
    if b:
        min_ = min(min_, money)
    
if min_ == 10**15:
  print(-1)
else:
    print(min_)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
a=[]
costs=[]
for _ in range(n):
    nl = list(map(int,input().split()))
    costs += [nl[0]]
    nl = nl[1:]
    a += [nl]

from itertools import product

ans = 10**16

for i in range(2**n):
    f = bin(i)[2:]
    f = "0"*(n-len(f)) + f
    f = [int(k) for k in f]
    total = [0]*m
    cost = 0
    for i in range(n):
        if f[i]:
            cost += costs[i]
            for j in range(m):
                total[j] += a[i][j]
    if min(total) >= k:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import*
n, m, x = map(int, input().split())
d = [list(map(int, input().split())) for k in range(n)]
INF = float("inf")
mi = INF
for i in range(1, n+1):
    for j in combinations(range(n), i):
        if all(sum(d[p][q] for p in j) >= x for q in range(1, m+1)):
            mi = min(mi, sum(d[c][0] for c in j))
print(mi if mi != INF else -1)

Submission status: Accepted

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

C = []
A = []

for i in range(N):
    c, *a = [int(n) for n in input().split()]
    C.append(c)
    A.append(a)

# C[N-1],A[N-1][M-1]

mc = -1
for k in range(2**N):
    kk = k
    rikai = [0] * M
    cost = 0
    for i in range(N):
        if kk & 1:
            cost += C[i]
            rikai = [r + a for (r, a) in zip(rikai, A[i])]
            if all([r >= X for r in rikai]):
                if mc == -1 or mc > cost:
                    mc = cost
        kk >>= 1

print(mc)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
books = [tuple(map(int, input().split())) for _ in range(N)]
MAX = 10**12
ans = MAX
for bit in range(1 << N):
    money = 0
    algo = [0] * M
    for i in range(N):
        if ((bit >> i) & 1) == 1:
            C, *A, = books[i]
            money += C
            for j, a in enumerate(A): algo[j] += a
    if any(a < X for a in algo): continue
    ans = min(ans, money)
print(ans if ans != MAX else -1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
book = []
cost = []
for i in range(N):
    c, *a, = list(map(int, input().split()))
    book.append(a)
    cost.append(c)
ans = float('inf')
for bit in range(1 << N):
    know = [0] * M
    costbit = 0
    flag = True
    for i in range(N):
        if bit & (1 << i):
            for j in range(M):
                know[j] += book[i][j]
            costbit += cost[i]
    for l in range(M):
        if know[l] < X:
            flag = False
    if flag:
        ans = min(ans, costbit)
if ans <= 1000000000:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
"""
algo1 algo2 algo3 
 0     0     0
"""
n, m, x = map(int, raw_input().split(' '))
books = [map(int, raw_input().split(' ')) for _ in range(n)]

def dfs(i, books, x, cc, knowledge, r):
	if i == len(books):
		if all([k>= x for k in knowledge]):
			r[0] = min(r[0], cc)
		return

	u = books[i]
	cost = u[0]
	book = u[1:]
	improvedknowledge = [k+book[ii] for ii,k in enumerate(knowledge)]
	
	dfs(i+1, books, x, cc + cost, improvedknowledge, r)
	dfs(i+1, books, x, cc, knowledge[::], r)

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, M, X = LI()
    C = [0]*N
    A = [[0]*M for _ in range(N)]
    for i in range(N):
        ca = LI()
        C[i] = ca[0]
        A[i] = ca[1:]

    cost_min = INF
    for i in range(2**N):
        cost = 0
        rikaido = [0]*M
        for j in range(N):
            if i>>j&1:
                cost += C[j]
                rikaido = [k+m for k, m in zip(rikaido, A[j])]
        if [j>=X for j in rikaido].count(True)==M:
            cost_min = min(cost, cost_min)

    if cost_min>=INF:
        print(-1)
    else:
        print(cost_min)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0] * N
A = []
for i in range(N):
    CA = list(map(int, input().split()))
    C[i] = CA[0]
    A.append(CA[1:])
INF = 1000000007

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

Submission status: Accepted

Solution code:
# C - Skill Up

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

n, m, x = map(int, input().split())
c = []
a = []
for i in range(n):
    row = list(map(int, input().split()))
    assert len(row) == 1 + m
    c.append(row[0])
    a.append(row[1:])

print(min((sum(c[i] for i in s) for s in powerset(range(n))
           if all(sum(a[i][j] for i in s) >= x for j in range(m))),
          default=-1))

Submission status: Accepted

Solution code:
# Code for C - Skill Up
# Use input() to fetch data from STDIN
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

[n, m, X] = map(int, input().split())
c = [0 for x in range(n)]
a = [[0 for x in range(m)] for y in range(n)]

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

costs = []
for s in powerset(range(n)):
    cost = 0
    t = [0 for x in range(m)]
    for x in s:
        cost += c[x]
        for y in range(m):
            t[y] += a[x][y]
    if all(map(lambda x: x >= X, t)):
        costs.append(cost)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
min_c = float('inf')
l = []
for i in range(n):
    ns = list(map(int, input().split()))
    l.append(ns)
for i in range(1, 2 ** n):
    flag = True
    a = bin(i)[2:].zfill(n)
    for j in range(m):
        s = 0
        for index, b in enumerate(a):
            if b == '1':
                s += l[index][j+1]
        if s < x:
            flag = False
            break
    if flag:
        min_c = min(min_c, sum(l[i][0] for i in range(n) if a[i] == '1'))
if min_c == float('inf'):
    print(-1)
else:
    print(min_c)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
ca = [[int(i) for i in readline().split()] for _ in range(n)]

from itertools import combinations
import numpy as np

lc = [i for i in range(n)]

ans = 1001001001

for nc in range(1,n+1):
    lc_sub = list(combinations(lc,nc))
    for lc_sub2 in lc_sub:
        tmp_price = 0
        tmp_und = np.array([0]*m)
        for c in lc_sub2:
            tmp_price += ca[c][0]
            tmp_und += np.array(ca[c][1:])
        if all([und >= x for und in tmp_und]):
            ans = min(ans, tmp_price)

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

Submission status: Accepted

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

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

for i in range(2**N):
    l = [0]*M
    cst = 0
    flag = True
    for j in range(N):
        if (i>>j) & 1:
            cst += C[j]
            for k in range(M):
                l[k] += A[j][k]
    for k in range(M):
        if l[k] < X:
            flag = False
            break
    if flag:
        if cst < min_cst or min_cst == -1:
            min_cst = cst

print(min_cst)

Submission status: Accepted

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

mini = 12 * 100000 + 1
for bit in range(1<<N):
    A_sum = [0] * M
    price = 0
    for i in range(N):
        if (bit >> i) & 1:
            price += C[i]
            for j in range(M):
                A_sum[j] += A[i][j]
    flug = True
    for i in A_sum:
        if i < X:
            flug = False
            break
    if flug:
        mini = min(mini, price)
if mini == 12 * 100000 + 1: print(-1)
else: print(mini)

Submission status: Accepted

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

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

ans = float('inf')

for i in range(2**N):
    cost = 0
    A = [0] * M
    for j in range(N):
        if i >> j & 1 == 1:
            cost += CA[j][0]
            for m in range(M):
                A[m] += CA[j][m+1]

    flg = True
    for m in range(M):
        if A[m] < X:
            flg = False
            break
    if flg:
        ans = min(ans, cost)

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

Submission status: Accepted

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

from itertools import combinations
a = []
for i in range(n):
    a.append([int(i) for i in input().split(' ')])
min_cost = float('inf')
for i in range(1, n + 1):
    for opt in combinations(range(n), i):
        curr_cost = 0
        curr_skills = [0] * m
        for to_take in opt:
            curr_cost += a[to_take][0]
            for j in range(1, m + 1):
                curr_skills[j - 1] += a[to_take][j]
        found = True
        for j in range(m):
            if curr_skills[j] < x:
                found = False
        if found:
            min_cost = min(min_cost, curr_cost)
print(min_cost if min_cost != float('inf') else -1)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
ca=np.array(ca)
ans=np.array([])
ans_list=np.array([])
for i in range(2**n):
  flag=True
  ans=np.array([0]*(m+1))
  for j in range(n):
    if (i>>j)&1:
      ans+=ca[j]
  for i in range(1,len(ans)):
    if x>ans[i]:
      flag=False
      break
  if flag==True:
    ans_list=np.append(ans_list,ans[0])
if len(ans_list)>=1:
  print(int(min(ans_list)))
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n, m, x = map(int, input().split())
flag = 0

cs = []
a = []
for i in range(n):
    inputs = [int(x) for x in input().split()]
    ci = inputs[0]
    ai = inputs[1:]
    cs.append(ci)
    a.append(ai)

res = 99999999999
for num in itertools.product('01', repeat=n):
    tmp = np.zeros(m)
    cost = 0
    for j in range(n):
        if num[j] == '0':
            continue
        else:
            cost += cs[j]
            tmp += np.array(a[j])
    if sum(tmp >= x) == m:
        flag = 1
        res = min(res, cost)

if flag:
    print(res)
else:
    print(-1)

Submission status: Accepted

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

ans = float('inf')
def dfs(i, now, cost):
    global ans
    if i == N:
        if all(elem >= X for elem in now):
            ans = min(cost, ans)
    else:
        dfs(i+1, now, cost)
        A = C_A[i][1:]
        now_next = [x + y for (x, y) in zip(now, A)]
        dfs(i+1, now_next, cost+C_A[i][0])

dfs(0, [0]*M, 0)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 20:54:30 2020

@author: Kanaru Sato
"""

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

mincost = 10**9

for state in range(2**n):
    rikaido = [0 for i in range(m)]
    rikaishita = 1
    cost = 0
    for k in range(n):
        if (state&(1<<k))>>k:
            cost += costs[k]
            for i in range(m):
                rikaido[i] += a[k][i]
    for i in range(m):
        if rikaido[i] < x:
            rikaishita = 0
    if rikaishita == 1:
        mincost = min(mincost,cost)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
ans = [0] * M

book = []

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

def check(ans):
    for i in range(len(ans)):
        if ans[i] < X:
            return 0
    return 1

price_sum = float("inf")
for i in range(2 ** N):
    ans = [0] * M
    tmp = 0
    for j in range(N):
        if (i >> j & 1):
            tmp += book[j][0]
            for k in range(1, M+1):
                ans[k-1] += book[j][k]
    if check(ans):
        price_sum = min(price_sum, tmp)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,M,X = mis()
    B = [lmis() for _ in range(N)]
    ans = INF
    for b in range(2**N):
        pt = [0]*(M+1)
        for i in range(N):
            if (1<<i)&b:
                for j in range(M+1):
                    pt[j] += B[i][j]
        if min(pt[1:])>=X:
            ans = min(ans, pt[0])
    print(ans if ans!=INF else -1)




main()

Submission status: Accepted

Solution code:
# n = 参考書
# m = あるごズム和
# x = すべての理解度
import itertools
n, m, x = map(int, input().split())

books = []
able = [0 for _ in range(m)]

for i in range(n):
    book = list(map(int, input().split()))
    books.append(book)
    for idx, j in enumerate(book[1:]):
        able[idx - 1] += j

if min(able) < x:
    print(-1)
    exit()

ans = float('INF')
for flags in list(itertools.product(range(2), repeat=n)):
    able = [0 for _ in range(m)]
    cost = 0
    for bo, flag in enumerate(flags):
        if flag:
            book = books[bo]
            for idx, j in enumerate(book):
                if idx == 0:
                    cost += j
                else:
                    able[idx - 1] += j

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

print(ans)

Submission status: Accepted

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


def solve(i, j, item):
    if i == N:
        for k in item:
            if k < X:
                return float("inf")
        return j

    return min([solve(i + 1, j + item_list[i][0], item + item_list[i][1:]), solve(i + 1, j, item)])


ans = solve(0, 0, [0 for i in range(M)])
if ans != float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

ans = 1000000000
for i in range(1 << n):
     score = [0 for _ in range(m)]
     tmp = i
     t = 0
     for j in range(n):
         if tmp & 1:
             for k in range(m):
                 score[k] += ca[j][k + 1]
             t += ca[j][0]
         tmp >>= 1
     if x <= min(score):
         ans = min(ans, t)
if ans == 1000000000:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
G = []
ans = float('inf')
for _ in range(n):
    G.append(list(map(int, input().split())))
for i in range(1<<n):
    dummy = 0
    l = [0]*m
    flag = True
    for j in range(n):
        if (i>>j)&1 == 1:
            for k in range(m):
                l[k] += G[j][k+1]
            dummy += G[j][0]
    for p in range(m):
        if l[p] < x:
            flag = False
            break
    if flag == True:
        ans = min(ans, dummy)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
info=[]
for i in range(n):
    z=list(map(int,input().split()))
    info.append(z)
ans=10**9
for i in range(2**n):
    skill=[x]*m
    total=0
    for j in range(n):
        if (i>>j)&1: #j番目の本を買う
            total+=info[j][0]
            for k in range(m):
                skill[k]-=info[j][1+k]
            flag=True
            for k in range(m):
                if 0<skill[k]:
                    flag=False
                    break
            if flag:
                if total<ans:
                    ans=total
print(ans if ans<10**9 else -1)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from itertools import product

N,M,X=map(int,input().split())
a = [list(map(int,input().split())) for _ in range(N)]
res = 10**18
gen = [0,1]
for ls in product(gen,repeat=N):
    tmp = 0
    tmp2 = [0]*M
    for i in range(N):
        if ls[i] == 1:
            tmp += a[i][0]
            for j in range(M):
                tmp2[j] += a[i][j+1]
    for j in range(M):
        if tmp2[j] < X:
            tmp = 10**18
            break
    if tmp < res:
        res = tmp

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
import math

N , M , X = map(int,input().split())
data = []
[data.append(list(map(int,input().split()))) for _ in range(N)]
ten = 1000000 * 12
ans = 1000000 * 12
for x in range(2**N):
    bi = bin(x)[2::][::-1]
    tmp = [0] * M
    cost = 0
    for index , b in enumerate(bi) :
        if b == "1":
            cost += data[index][0]
            for i , d in enumerate(data[index][1::]):
                tmp[i] += d
    flag = 0
    for tt in tmp :
        if tt < X:
            flag = 1
            break
    if flag == 0:
        ans = min(cost , ans)

if ans == ten :
    ans = -1
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)]
ans=100000000000000000
for i in range(2**n):
    check=[0]*m
    ans_=0
    for j in range(n):
        if ((i>>j)&1):
            ans_+=ca[j][0]
            for k in range(m):
                check[k]+=ca[j][k+1]
    #print(ans_)
    if all([l>=x for l in check]):
        #print(ans_)
        ans=min(ans,ans_)
if ans==100000000000000000:
    print(-1)
else:
    print(ans)

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

res = float('inf')
for r in range(N + 1):
    for c in combinations(range(N), r):
        skills = [0] * M
        price = 0
        for i in c:
            price += books[i][0]
            for j, a in enumerate(books[i][1:]):
                skills[j] += a
        if all(skill >= X for skill in skills):
            res = min(res, price)

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

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n, m, x = MII()
    query = [MII() for _ in range(n)]
    mincost = 10**7
    for bit in range(1<<n):
        vals = [0]*m
        cost = 0
        for i in range(n):
            if bit&(1<<i):
                cost += query[i][0]
                for i, c in enumerate(query[i][1:]):
                    vals[i] += c
                x_g = [1 for v in vals if v >= x]
                if sum(x_g) == m:
                    mincost = min(cost, mincost)
    if mincost == 10**7:
        print(-1)
    else:
        print(mincost)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
C = []
A = []
for _ in range(n):
  c, *a = map(int,input().split())
  C.append(c)
  A.append(a)

queue = [(0,[0 for _ in range(m)],0)]
ans = float('inf')
while queue:
  cost, learn, index = queue.pop(-1)
  if all([l>= x for l in learn]):
    ans = min(ans, cost)
    continue
  if index == n:
    continue
  else:
    queue.append((cost, learn, index+1))
    queue.append((cost+C[index], [learn[i]+A[index][i] for i in range(m)], index+1))
    
print(ans if ans != float('inf') else -1)

Submission status: Accepted

Solution code:
import itertools

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

ans = float("inf")
for x in list(itertools.product([0,1], repeat=N)):
    tmp = 0
    tmp_A = [0] * M
    for i in range(N):
        if x[i] == 1:
            tmp += CA[i][0]
            for j in range(M):
                tmp_A[j] += CA[i][1+j]
    if min(tmp_A) >= X:
        ans = min(ans, tmp)

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 全探索
N, M, X = lr()
CA = np.array([lr() for _ in range(N)])
INF = 10 ** 9
answer = INF
for pattern in range(1<<N):
    temp = 0
    algo = np.zeros(M+1, dtype=np.int32)
    for i in range(N):
        if (pattern>>i) & 1:
            algo += CA[i]
    if np.all(algo[1:] >= X) and algo[0] < answer:
        answer = algo[0]

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

Submission status: Accepted

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

maxa = [0 for i in range(m)]
for i in range(n):
    for j in range(m):
        maxa[j] += ca[i][j+1]
ans = 10**7
for i in range(m):
    if maxa[i] < x:
        ans = -1
        break

#print(maxa)

def sankousyo(l):
    if len(l) == n:
    #    print(l)
        global ans
        kingaku = 0
        maxa_k = [0 for i in range(m)]
        for i in range(n):
            if l[i] == 1:
                for j in range(m):
                    maxa_k[j] += ca[i][j+1]
        for i in range(m):
            if maxa_k[i] < x:
                kingaku = -1
                break
        if kingaku != -1:
            for i in range(n):
                if l[i] == 1:
                    kingaku += ca[i][0]
            ans = min(ans,kingaku)
    else:
        sankousyo(l+[0])
        sankousyo(l+[1])
    
if ans == 10**7:
    sankousyo([])

print(ans)

Submission status: Accepted

Solution code:
n , m , x = map(int,input().split())
san = []
for i in range(n):
    san.append(list(map(int,input().split())))
ans = 10**8
for b in range(2**n):
    bs = format(b, 'b')
    bs = str(bs).rjust(n,'0')
    one = 0
    p = [0 for i in range(m)]
    for i in range(n):
        if bs[i] == "1":
            one += san[i][0]
            for j in range(1,m+1):
                p[j-1] += san[i][j]
    if min(p) >= x:
        ans = min(ans,one)
if ans == 10**8:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

L=[]
for i in range(N):
    l=list(map(int,input().split()))
    L.append(l)
#print(L)

ans=10**9
for i in range(2**N):
    I=i
    cost=0
    LIST=[]
    for j in range(N):
        if I//(2**(N-1-j))==1:
            LIST.append(L[j])
        I%=(2**(N-1-j))
    #print(LIST)
    for j in range(len(LIST)):
        cost+=LIST[j][0]
    if cost<ans:
        Sum=[0 for i in range(M)]
        for j in range(len(LIST)):
            for k in range(M):
                Sum[k]+=LIST[j][k+1]
        #print(Sum,cost,min(Sum))
        if min(Sum)>=X:
            ans=cost
if ans==10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
lst=[[0 for e in range(M+1)] for f in range(N)]
for i in range(N):
 lst[i]=list(map(int,input().split()))
F=10**7
for i in range(2**N):
 E=0
 Sui=[0]*N
 for j in range(N):
  if ((i >> j) & 1):
   Sui[j]+=1
 skl=[0]*M
 cost=0
 for k in range(N):
  if Sui[k]==1:
   for t in range(M):
    skl[t]+=lst[k][t+1]
   cost+=lst[k][0]
 E=0
 for t in range(M):
  if skl[t]>=X:
   E+=1
 if E==M:
  F=min(cost,F)
if F==10**7:
 print(-1)
else:
 print(F)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10**9)

def main():
    N,M,X = map(int,input().split())
    book = [[] for _ in range(N)]
    for i in range(N):
        book[i] = list(map(int,input().split()))

    INF = 10**20
    ans = INF
    for i in range(2**N):
        cost = 0
        algs = [0]*M
        for j in range(N):
            if (i >> j) & 1:
                cost += book[j][0]
                for k in range(M):
                    algs[k] += book[j][k+1]

        ng = False
        for alg in algs:
            if alg < X:
                ng = True

        if not ng:
            ans = min(ans,cost)

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


if __name__ == "__main__":
  main()