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())
bk = [list(map(int, input().split())) for _ in range(n)]
pr = 10 ** 7
for i in range(2 ** n):
    ef = [0] * (m + 1)
    for j in range(n):
        if i >> j & 1:
            ef = [p + q for (p, q) in zip(ef, bk[j])]
    for k in range(1, m + 1):
        if ef[k] < x:
            break
        if k == m:
            pr = min(pr, ef[0])
print(pr if pr != 10 ** 7 else -1)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

N,M,X = LI()
# c=[]
# a=[]
# for i in range(n):
#     ca = LI()
#     c.append(ca[0])
#     a.append(ca[1:])
# print(c)
# print(a)

_ca = [LI() for _ in range(N)]
ca = np.array(_ca, np.int64)
# print(ca)
# ca = ca.reshape(n,-1)
C = ca[:,0]
A = ca[:,1:]
# print(c)
# print(a)

result = 10**7
# ビット全探索
for i in range(1 << N):
    t = [0] * M
    c = 0
    for j in range(N):
        # i を j回右にシフトして1との論理積を取り、1であればアイテムを購入しているとみなす
        # 購入していない場合
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    # 全てX以上であれば更新
    if all(x >= X for x in t):
            result = min(result, c)

if result == 10**7:
    print(-1)
else:
    print(result)

Submission status: Accepted

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

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

money_min = 100000000
for bit in range(1 << N):
	bag = []
	for i in range(N):
		if ((bit >> i) & 1):
			bag.append(l[i])
	skill = [0]*M
	enough = [0]*M
	money = 0
	for sub in bag:
		money += sub[0]
		#print(money)
		for j in range(M):
			skill[j] += sub[j+1]
		#print(skill)
	for k in range(M):
		if skill[k] >= X:
			enough[k] += 1
		else:
			enough[k] = enough[k]
	if 0 not in enough:
		if money < money_min:
			money_min = money
		else:
			money_min = money_min

if money_min != 100000000:
	print(money_min)
else:
	print(-1)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

n, _, x = map(int, input().split())
arr1 = np.array([list(map(int, input().split())) for _ in range(n)])
ans = 1200000
if np.all(arr1.sum(0)[1:] >= x):
    for i in product((0, 1), repeat=n):
        arr2 = (i * arr1.T).sum(1)
        if np.all(arr2[1:] >= x):
            ans = min(ans, arr2[0])
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

    def _judge(pick_pattern: str) -> int:
        price = 0
        level = [0] * M
        # 金額と理解度の合計をそれぞれ求める
        for i in range(N):
            if pick_pattern[i] == "0":
                continue
            price += C[i]
            for j in range(M):
                level[j] += A[i][j]
        # 理解度の目標を達成しているかどうかを判定
        for j in range(M):
            if level[j] < X:
                return -1
        return price

    ans = 1001001001
    for i in range(2**N):
        pick = f"{i:b}".zfill(N)
        price = _judge(pick)
        if price > 0:
            ans = min(price, ans)

    print(ans if (ans < 1001001000) else -1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

c = [0]*n
a = [0]*n

for i in range(n):
    c[i],a[i] = ca[i][0],ca[i][1:]

INF = 10**9
ans  = INF

for i in range(1<<n):
    understanding = [0]*m
    cost = 0
    for j in range(n):
        if ((i>>j)&1):
            cost += c[j]
            for k in range(m):
                understanding[k] += a[j][k]
    ok = True
    for s in range(m):
        if understanding[s] < x:
            ok = False
    if ok:
        ans = min(ans, cost)

if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N, M, X = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
flug = True
for j in range(1, M + 1):
    sum_test = 0
    for i in range(N):
        sum_test += A[i][j]
    if sum_test < X:
        flug = False
        break
N_idx = [n for n in range(N)]
rec_tes = 0
for i in range(N):
    rec_tes += A[i][0] 
for i in range(N):
    for j in combinations(N_idx, r = i + 1):
        for k in range(1, M + 1):
            sum_und = 0
            sum_tes = 0
            for h in j:
                sum_und += A[h][k]
                sum_tes += A[h][0]
            if sum_und < X:
                break
        if sum_und >= X and sum_tes < rec_tes:
            rec_tes = sum_tes
if flug:
    print(rec_tes)
else:
    print(-1)

Submission status: Accepted

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

INF = 10**9
ans = INF
for i in range(2**n):
    cost = 0
    y = [0]*m
    for j in range(n):
        flg = i & 1
        if flg:
            cost += a[j][0]
            for cm in range(m):
                y[cm] += a[j][cm+1]
        i >>= 1
    for cm in range(m):
        if y[cm] < x:
            break
        if cm == m-1:
            ans = min(ans, cost)
print(ans) if ans < INF else print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
book_lists = [list(map(int, input().split())) for _ in range(N)]
max_cost = 10**5*12+1
min_cost = max_cost

for i in range(1, 2**N):
   score_list = [0 for _ in range(M)]
   cost = 0
   for j in range(N):
       if i >> j & 1:
           cost += book_lists[j][0]
           for k in range(M):
               score_list[k] += book_lists[j][k+1]
   if min(score_list) >= X:
       min_cost = min(cost, min_cost)

print(min_cost if not min_cost == max_cost else -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):
    bag=[0 for _ in range(m)]
    total=0
    res=True
    for j in range(n):
        if ((i>>j)&1):
            total+=a[j][0]
            for k in range(m):
                bag[k]+=a[j][k+1]
    for l in range(m):
        if bag[l]<x:
            res=False
            break
    if res:
        ans.append(total)

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        book = tuple(map(int, input().split()))
        books.append(book)
    pro = product((1, 0),repeat=n)
    costs = []

    for proe in pro:
        cost = 0
        algo = [0] * m
        for i1, proee in enumerate(proe):
            if proee:
                cost += books[i1][0]
                for al in range(1, m + 1):
                    algo[al-1] += books[i1][al]
        if all([i >= x for i in algo]):
            costs.append(cost)
    if not costs:
        print(-1)
    else:
        print(min(costs))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        book = tuple(map(int, input().split()))
        books.append(book)
    pro = product((1, 0),repeat=n)
    costs = []

    for proe in pro:
        cost = 0
        algo = [0] * m
        for i1, proee in enumerate(proe):
            if proee:
                cost += books[i1][0]
                for al in range(1, m + 1):
                    algo[al-1] += books[i1][al]
            if all([i >= x for i in algo]):
                costs.append(cost)
    if not costs:
        print(-1)
    else:
        print(min(costs))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        book = tuple(map(int, input().split()))
        books.append(book)
    pro = product((1, 0),repeat=n)
    costs = []

    for proe in pro:
        cost = 0
        algo = [0] * m
        for i1, proee in enumerate(proe):
            if proee:
                cost += books[i1][0]
                for al in range(1, m + 1):
                    algo[al-1] += books[i1][al]
                if all([i >= x for i in algo]):
                    costs.append(cost)
    if not costs:
        print(-1)
    else:
        print(min(costs))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N,M,X = map(int,input().split())
ca=np.array([0]*(M+1))
ans = 10**7

for i in range(N):
    ca=np.vstack([ca,[int(i) for i in input().split()]])

for i in range(2**N):

    need_skills=np.array([0]+[X]*M)

    buy_item = [0]*N
    for j in range(N):
        if (i>>j)&1:
            buy_item[j]=1

    for k in range(N):
        need_skills -= ca[k+1]*buy_item[k]

    if np.all(need_skills<=0):
        ans = min(ans,-need_skills[0])

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

Submission status: Accepted

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

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


def calc_cost(li):
    """
    与えられた部分リストが各アルゴリズムの条件を
    満たすか確認し、そのコストを計算。
    条件満たさないときは100000000を出力
    """

    # flag = True
    cost = 0
    for item in li:
        cost += item[0]

    for i in range(M):
        algo_sum = 0
        for item in li:
            algo_sum += item[i + 1]
        if algo_sum < X:
            return 100000000

    return cost


cost = 100000000
for i in range(2 ** N):
    in_list = []
    for j in range(N):
        if (i >> j) & 1:
            in_list.append(list[j])

    temp_cost = calc_cost(in_list)
    if temp_cost == -1:
        break
    cost = min(cost, temp_cost)

if cost == 100000000:
    cost = -1

print(cost)

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

prices = []
best_skill = [0]*m
for i in range(1, n+1):
    n_list = [i for i in range(n)]
    for N in itertools.combinations(n_list, i):
        skill = [0]*m
        price = 0
        for j in N:
            price += ca[j][0]
            for k in range(1, m+1):
                skill[k-1] += ca[j][k]
        if min(skill) >= x:
            prices.append(price)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, m, x = Is()
books = []
for _ in range(n):
  xs = Is()
  cost = xs[0]
  skills = xs[1:]
  books.append((cost, skills))

ans = []
stack = [(0, books, [0] * m)]

def doit(cost, books, skills):
  book = books[0]
  books = books[1:]
  
  ns = np.add(skills, book[1])
  if all([n >= x for n in ns]):
    ans.append(cost + book[0])
    
  if books:
    stack.append((cost+book[0], books, ns))
    stack.append((cost, books, skills))

while stack:
  state = stack.pop(0)
  doit(state[0], state[1], state[2])

print(min(ans) if ans else '-1')

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(n)]
a=[]
ans=[]
for i in range(2**n):
    b=bin(i)[2:].zfill(n)
    a.append(b)
for bit in a:
    Skills=[]
    for i in range(1,1+m):
        skill=0
        for j in range(n):
            if bit[j]=="1":
               skill+=A[j][i]
        Skills.append(skill)
    cost=0
    if min(Skills)>=x:
        for j in range(n):
            if bit[j]=="1":
                cost+=A[j][0]
        ans.append(cost)
if len(ans)==0:
    ans.append(-1)
print(min(ans))

Submission status: Accepted

Solution code:
N, M, X = list(map(int, input().split()))
A = []
for i in range(N):
    s = list(map(int, input().split()))
    t = [s[j] for j in range(1, M+1)]
    A.append([s[0], t])
# print(A)

# 下からj番目のbitが1->本jを買う
# B[i]がすべてX以上になればOK
ans = []
for i in range(2**N):
    price = 0
    B = [0]*M
    for j in range(N):
        if (i >> j) & 1:
            price += A[j][0]
            for k in range(M):
                B[k] += A[j][1][k]
    # print(i,[B[k]for k in range(M)])
    for k in range(M):
        if B[k] < X:
            break
    else:
        ans.append(price)

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

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

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

c = []
a = []

for _ in range(N):
    k = list(map(int, input().split()))
    c.append(k[0])
    a.append(k[1:])
    
cost = []

for i in range(1, N+1):
    l = list(combinations(range(N),i))
    for ls in l:
        cs = 0
        x = np.full(M,0)
        for n in ls:
            cs += c[n]
            x += np.array(a[n])
        if all(x >= X):
            cost.append(cs)

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

Submission status: Accepted

Solution code:
n,m,x,*book=map(int,open(0).read().split())
ans=10**10

for i in range(2**n):
    j=i
    k=0
    cur=0
    curskill=[0]*m
    while j>0:
        if j&1:
            cur+=book[k*(m+1)]
            for l in range(1,m+1):
                curskill[l-1]+=book[k*(m+1)+l]
        j=j>>1
        k+=1
    
    for j in range(m):
        if curskill[j]<x:
            break
    else:
        ans=min(ans,cur)

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

Submission status: Accepted

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

ans = 10**10

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

for i in range(1 << n):
    skill = [0] * m
    total_cost = 0
    for j in range(n):
        if (i>>j) & 1:
            total_cost += c[j]
            skill = [skill[t] + a[j][t] for t in range(m)]
    if all (y >= x for y in skill):
        ans = min(ans, total_cost)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
a = [0]*n
for i in range(n):
    a[i] = list(map(int,input().split()))
ans = float("Inf")
for i in range(2**n):
    c = 0
    L = [0]*m
    for j in range(n):
        if (i>>j)&1:
            c += a[j][0]
            for k in range(m):
                L[k] += a[j][k+1]
    
    sw = 1
    for k in range(m):
        if L[k] < x:
            sw = 0
            break
    if sw == 1:
        ans = min(ans, c)
        
if ans == float("Inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
# import math
# import sys
import numpy as np

# K = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M, X = map(int, input().split())
# H = list(map(int, input().split()))
# Q = list(map(int, input().split()))
# S = input()

# d = sorted(d.items(), key=lambda x:x[0]) # keyでsort
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement([i for i in range(1, M + 1)], N))
# print(a[0][0])
# print(conditions[0])

conditions = []
for i in range(N):
    CA = list(map(int, input().split()))
    conditions.append(CA)
conditions = np.array(conditions)
pattarns = list(itertools.product((0,1), repeat=N))

min_clear_cost = 10**20
for pattarn in pattarns:
    cost = 0
    A = np.zeros(M)
    for i, j in enumerate(pattarn):
        if j == 1:
            cost += conditions[i][0]
            A += conditions[i][1:]
    if min(A) >= X and min_clear_cost > cost:
        min_clear_cost = cost

if min_clear_cost == 10**20:
    min_clear_cost = -1

print(min_clear_cost)

Submission status: Accepted

Solution code:
def main():
    n,m,x = map(int,input().split())
    c = []
    a = []
    for _ in range(n):
        ca = [int(v) for v in input().split()]
        c.append(ca[0])
        a.append(ca[1:])
    
    INTHIGH = 1<<32
    pricemin = INTHIGH
    for i in range(1<<n):
        sm = [0]*m
        sc = 0
        for j in range(n):
            if i & 1<<j:
                sc += c[j]
                for k in range(m):
                    sm[k] += a[j][k]
                if min(sm)>=x:
                    pricemin = min(pricemin, sc)
                    break

    print(pricemin if pricemin<INTHIGH else -1) 

main()

Submission status: Accepted

Solution code:
def oginau(k):
  if len(k)!=N:
    k=str(("0"*(N-len(k)))+k)
    return k
  else:
    return k
N,M,X=map(int,input().split())
L=[[] for i in range(N)]
for i in range(N):
  L1=list(map(int,input().split()))
  L[i]=L1
mina=10**10
for i in range(2**N):
  R=[0 for i in range(M)]
  money=0
  s=str(bin(i)[2:])
  s=oginau(s)
  for j in range(N):
    if s[j]=="1":
      money+=L[j][0]
      for w in range(1,M+1):
        R[w-1]+=L[j][w]
  if len([i for i in R if i>=X])==M:
    mina=min(money,mina)
if mina==10**10:
  print(-1)
else:
  print(mina)

Submission status: Accepted

Solution code:
import numpy as np

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

ans = -1
for i in range(2 ** n):
    total = 0
    skill = np.zeros(m)
    for j in range(n):
        if (i >> j) & 1:
            total += cost[j]
            skill += a[j]
    if (all(skill >= x)):
        if (ans == -1):
            ans = total
        else:
            ans = min(ans, total)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

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

    ans = 10 ** 7
    for bit in range(1 << N):
        res = [0 for _ in [0] * (M + 1)]
        for i in range(N):
            if bit & (1 << i):
                res = [a + b for a, b in zip(res, A[i])]
        if all(a >= X for a in res[1:]):
            ans = min(ans, res[0])
    if ans == 10 ** 7:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class book:
    def __init__(self, C, A):
        self.C = C
        self.A = A
N, M, X = [int(i) for i in input().split()]
P = []
for i in range(N):
    tmp = [int(i) for i in input().split()]
    C = tmp.pop(0)
    P.append(book(C, tmp))

learn = [0 for i in range(M)]
minc = 10**7
flag = 0
for i in range(2 ** N):
    csum = 0
    for j in range(M):
        learn[j] = 0
    for j in range(N):
        if ((i >> j) & 1):
            csum += P[j].C
            for k in range(M):
                learn[k] += P[j].A[k]
    if min(learn) >= X:
        flag = 1
        if minc > csum:
            minc = csum
if flag == 1:
    print(minc)
else:
    print(-1)

Submission status: Accepted

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

c = []
a = []

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

cnt = 0

cost_t = n*10**5

for i in range(2**n):
    argo = [0 for _ in range(m)]
    cost = 0
    for j in range(n):
        if ((i >> j) & 1):
            cost += c[j]
            for k in range(m):
                argo[k] += a[j][k]

    if min(argo) >= x:
        cnt += 1
        if cost < cost_t:
            cost_t = cost
        
if cnt == 0:
    print(-1)
else:
    print(cost_t)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
A = [[] for i in range(m)]
eff = [[] for i in range(m)]
price = []
for a in range(n):
    a = list(map(int, input().split()))
    price.append(a[0])
    for j in range(m):
        A[j].append(a[j+1])


for a in A:
    if sum(a) < x:
        print(-1)
        exit()


min_money = 1<<30
for bits in range(1<<n):
    sum_temp = [0] * m
    sum_money = 0
    for j in range(n):
        if bits>>j & 1:
            sum_money += price[j]
            for i in range(m):
                sum_temp[i] += A[i][j]
    else:
        ok = True
        for i in sum_temp:
            if i < x:
                ok = False
                break
        if ok:
            min_money = min(min_money, sum_money)



print(min_money)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
price = []
A = []
for i in range(n):
    l = list(map(int,input().split()))
    price.append(l[0])
    A.append(l[1:])
# print(A,price)

mini = 10**7

for biti in range(1<<n):
    comprehension = [0]*m
    value = 0
    for i in range(n):
        if (biti >> i & 1):
            for j in range(m):
                comprehension[j] += A[i][j]
            value += price[i]
    flag = True
    for com in comprehension:
        if com < x:
            flag = False
    if flag:
        mini = min(mini,value)
if mini == 10**7:
    print(-1)
else:
    print(mini)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
a=2**64
b=[np.array(list(map(int,input().split())),"i8")for i in range(n)]
for i in range(2**n):
    c=bin(i)[2:]
    c="0"*(n-len(c))+c
    l=np.zeros(m)
    q=0
    for j in range(n):
        if c[j]=="1":
            q+=b[j][0]
            l+=b[j][1:]
    if np.min(l)>=x:
        a=min(a,q)
if a==2**64:
    print(-1)
else:
    print(a)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
C = []
A = []
for i in range(N):
    L = list(map(int,input().split()))
    C.append(L[0])
    A.append(L[1:M+1])
import itertools
L = []
Num = [i for i in range(N)]
for i in range(1,N+1):
    for j in itertools.combinations(Num,i):
        L.append(list(j))
c = 20000000
for i in range(len(L)):
    Z = [0 for _ in range(M)]
    m = 0
    for j in range(len(L[i])):
        for k in range(M):
            Z[k] += A[L[i][j]][k]
        m += C[L[i][j]]
    for l in range(M):
        if Z[l] < X:
            break
        if l == M-1:
            c = min(c,m)
if c == 20000000:
    print(-1)
else:
    print(c)

Submission status: Accepted

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

c = [0] * n
a = [[0] * m for _ in range(n)]

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

INF = 10 ** 9
ans = INF

for i in range(1 << n):
    cost = 0
    under = [0] * m
    for j in range(n):
        if not i >> j & 1: continue
        cost += c[j]
        for k in range(m):
            under[k] += a[j][k]
    ok = True
    for k in range(m):
        if under[k] < x: ok = False
    if ok:
        ans = min(ans, cost)

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

Submission status: Accepted

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

ans=[]
for i in range(2**n):
    t=[0]*m
    cost=0
    for j in range(n):
        if (((i>>j)&1)==1):
            for k in range(m):
                t[k]+=l[j][k+1]
            cost+=l[j][0]
    
    #print('i',i,bin(i),min(t),cost)
    if min(t)>=x:
        ans.append(cost)

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

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int, input().split())
a = [list(map(int, input().split())) for l in range(n)]
bit=list(itertools.product([0,1],repeat=n))
M=10**7
for i in range(2**n):
  cnt1=[0]*m
  cnt2=0
  for j in range(n):
    if bit[i][j]==1:
      cnt2+=a[j][0]
      for k in range(m):
        cnt1[k]+=a[j][k+1]
  ans=True
  for j in range(m):
    if cnt1[j]<x:
      ans=False
  if ans:
    M=min(cnt2,M)
if M==10**7:
  print(-1)
else:
  print(M)

Submission status: Accepted

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

N=[]
NI=[]
for i in range(n) :
    N = list(map(str, input().split()))
    NI.append(N)

ans=-1

for i in range(1<<n) :
    A=[0]*(m+1)
    for j in range(n) :
        # print(NI[j])
        if (1<<j)&i :
            A=[x+int(y) for(x,y)in zip(A,NI[j])]
    # print(A)
    a = A[0]
    del A[0]
    if min(A)<x :
        a=-1
    elif ans==-1:
        ans = a
    elif ans>a :
        ans = a
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [0] * n
a = [[0] * m for i in range(n)]
for i in range(n):
    b = list(map(int, input().split()))
    c[i], a[i] = b[0], b[1::]

ans_money = 1200001

for i in range(2**n):
    b = [0]*m
    sum_money = 0
    for l in range(n):
        if i>>l & 1:
            for k in range(m):
                b[k] += a[l][k]            
            sum_money += c[l]
    if all(elem >= x for elem in b) and sum_money < ans_money:
        ans_money = sum_money
if ans_money == 1200001:
    print(-1)
else:
    print(ans_money)

Submission status: Accepted

Solution code:
import math
def facts(n):
    ans = []
    for  i in range(1, int(math.sqrt(n)+1)):
        if(n%i==0):
            ans.append(i)
            ans.append(n//i)
    ans = sorted(ans)
    return ans


n,m, x = map(int, input().split())
arr = []
narr = [0 for i in range(m)]
ans = 123456789
for i in range(n):
    tarr = list(map(int, input().split()))
    arr.append(tarr)
for i in range(1<<n):
    tarr = list(narr)
    cost = 0
    for a in range(n):
        if((i>>a)&1):
            cost+=arr[a][0]
            for b in range(1, m+1):
                tarr[b-1] += arr[a][b]
    ok = True
    for i in range(m):
        if(tarr[i]<x):
            ok = False
            break
    if(ok):
        ans = min(ans, cost)
if(ans == 123456789):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

INF = 10**9
ans = INF


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

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



for s in range(0, 1 << n):
    smart = [0] * m
    cost_sum = 0
    for i in range(n):
        if (s >> i) % 2 == 0:
            continue
        cost_sum += C[i]
        for j in range(m):
            smart[j] += A[i][j]
    ok = True
    for j in range(m):
        if smart[j] < X:
            ok = False
    if ok:
        ans = min(ans, cost_sum)

if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for _ in range(N)]
max_=10**16
ans=max_
for bit in range(2**N):
  check=[0]*M
  ans_=0
  for i in range(N):
    if bit>>i&1:
      ans_+=CA[i][0]
      for j in range(M):
        check[j]+=CA[i][j+1]
  if all([k>=X for k in check]):
    ans=min(ans,ans_)
print(ans if ans!=max_ else -1)

Submission status: Accepted

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

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

Sum = [0] * (m + 1)
mincost = 999999999

for bit in range(1 << n):
	tmpcost = 0
	Sum = [0] * (m + 1)
	flag = False
	for i in range(0 , n):
		if ((bit >> i) & 1):
			tmpcost += a[i][0]
			for j in range(1 , m + 1):
				Sum[j] += a[i][j]
	for i in range(1 , m + 1):
		if Sum[i] < x:
			flag = True
			break
	if flag == False:
		mincost = min(mincost , tmpcost)

if mincost == 999999999:
	print(-1)
else :
	print(mincost)

Submission status: Accepted

Solution code:
scnum = list(map(int,input().split()))
score = [0]*scnum[0]
answer = 13*(10**5)
nowsum = 0
scosum = [0]*scnum[1]
gacchi = 0

for i in range(scnum[0]):
    score[i] = list(map(int,input().split()))
    
for j in range(2**scnum[0]):
    if j != 0:
        for h in range(scnum[0]):
            if (j>>h) & 1:
                nowsum += score[h][0]
                for k in range(scnum[1]):
                    scosum[k] += score[h][k+1]
        for l in range(scnum[1]):
            if scosum[l] >= scnum[2]:
                gacchi += 1
        if gacchi == scnum[1] and nowsum < answer:
            answer = nowsum
        nowsum = 0
        gacchi = 0
        scosum = [0]*scnum[1]

if answer == 13*(10**5):
    print(-1)
else:
    print(answer)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [(list(map(int, input().split()))) for _ in range(n)]
caca = [0]*(m+1)
ans = 12 * 10**5 +1
chk = 0
for nn in range(2**n):
    for j in range(m+1):
        caca[j] = 0
    cnt = 0
    for i in range(n):
        if (nn>>i) & 1:
            for j in range(m+1):
                caca[j] += ca[i][j]
    for j in range(1, m+1):
        if caca[j] >= x:
            cnt += 1
        else:
            break
    if cnt == m:
        ans = min(ans, caca[0])
        chk = 1
print(ans if chk == 1 else -1)