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 sys import stdin
input = stdin.readline

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

ans = -1

for i in range(2 ** N):
    A = [0] * M
    buy = 0
    for j in range(N):
        if (i >> j) & 1:
            buy += ca[j][0]
            for k in range(1, M + 1):
                A[k - 1] += ca[j][k]

    for i in range(M):
        if A[i] < X:
            break

        if i == M - 1:
            if ans == -1:
                ans = buy
            else:
                ans = min(ans, buy)

print(ans)

Submission status: Accepted

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

unds = [[0 for _ in range(M + 1)]]

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

    new_unds = list()
    for und in unds:
        new_und = copy.copy(und)
        new_und[-1] += C
        for m in range(M):
            new_und[m] += A[m]
        new_unds.append(new_und)
    unds.extend(new_unds)

minc = 10e10
for und in unds:
    for m in range(M):
        if und[m] < X:
            break
    else:
        if minc > und[-1]:
            minc = und[-1]

if minc > 10e9:
    minc = -1

print(minc)

Submission status: Accepted

Solution code:
import math

def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

# n = int(input())
# a, 
# s = input()

N, M, X = list(map(int, input().split()))
C = [0]*(N+1)
A = makelist(N+1, M+1)
for i in range(1, N+1):
    h = list(map(int, input().split()))
    C[i] = h[0]
    A[i] = h[1:]

ma = int(1e18)
ans = ma
for b in range(1 << N):
    ind = 1
    dp = [0]*M
    res = 0
    while b > 0:
        if b % 2 == 1:
            c = C[ind]
            l = A[ind]
            for i in range(M):
                dp[i] += l[i]
            res += c
            
        b //= 2
        ind += 1
    if all([e >= X for e in dp]):
        ans = min(ans, res)


if ans < ma:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

min_price = 100000000000
for i in range(2 ** N):
    price = 0
    understand = [0] * M
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            price += C[j]
            for k, u in enumerate(A[j]):
                understand[k] += u

    if min(understand) >= X:
        min_price = min(min_price, price)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for _ in range(n)]
ans=10**9
for i in range(2**n):
  cnt=[0]*m
  kari=0
  for j in range(n):
    if (i>>j)&1:
      for k in range(m):
        cnt[k]+=ca[j][k+1]
      kari+=ca[j][0]
    else:
      pass
  if min(cnt)>=x:
    ans=min(ans,kari)
if ans==10**9:
  print(-1)
else:
  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=10**18
x=[0]*M
for i in range(1,2**N):
  _ans=0
  _x=x[:]
  f=True
  for j in range(N):
    if i%2==1:
      for k,a in enumerate(CA[j]):
        if k==0:
          _ans+=a
        else:
          _x[k-1]+=a
    i=i//2
  for _ in _x:
    if _<X:
      f=False
      break
  if f:
    ans=min(ans,_ans)
if ans==10**18:
  ans=-1
print(ans)

Submission status: Accepted

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

    
opt_cost = 10 ** 10    
    
for i in range(2 ** N):
    temp_num = i
    lst_ = []
    for j in range(N):
        if temp_num % 2 == 0:
            lst_.append(0)
        else:
            lst_.append(1)
        temp_num = temp_num // 2
        
        
    temp_cost = 0
    temp_ability = [0 for n in range(M)]
    
    for k in range(N):
        if lst_[k] == 1:
            temp_cost += cost_[k]
            for a in range(M):
                temp_ability[a] += A[k][a]
    
    if min(temp_ability) >= X:
        if temp_cost <= opt_cost:
            opt_cost = temp_cost

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n, m, x = nm()
l = [nl() for _ in range(n)]
ans = 10**10
for bit in range(1<<n):
    cst = 0
    g = [0]*m
    for i in range(n):
        if bit & (1<<i):
            f = l[i]
            cst += f[0]
            for j in range(m):
                g[j] += f[j+1]
    if min(g) >= x:
        ans = min(ans, cst)
print(ans if ans < 10**10 else -1)

Submission status: Accepted

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

cost = 10 ** 7

for i in range(2 ** N):
    score = [0] * M
    r = str(format(i, 'b')).zfill(N)
    c = 0
    for j in range(N):
        if r[j] == '1':
            c += ABC[j][0]
            for k in range(M):
                score[k] = score[k] + ABC[j][1 + k]
    j = 1
    for k in range(M):
        if score[k] < X:
            j = 0
    if j == 1 and c < cost:
        cost = c
if cost == 10 ** 7:
    print(-1)
else:
    print(cost)

Submission status: Accepted

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

# bit長
bit_len = n
INF = 10 ** 7
ans = INF


for num in range(2 ** bit_len):
    tmp = [0 for i in range(m)]
    c = 0
    for i in range(bit_len):
        if num & (1 << i):
            # 処理
            c += ca[i][0]
            for j in range(1, m+1):
                tmp[j-1] += ca[i][j]
    if min(tmp) >= x:
        ans = min(ans, c)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m,x = list(map(int,input().split()))
c = [list(map(int,input().split())) for i in range(n)]
inf=float("inf")
ret = inf
#デカルト積。ネストしたforループと等価
from itertools import product
for flg_list in list(product([0,1],repeat=n)):
    rikaido_list = [0] * m
    cost = 0
    flg = True
    for i,v in enumerate(flg_list):
        if v == 1:
            cost += c[i][0]
            rikaido_list = [i+j for i,j in zip(rikaido_list,c[i][1::])]
    for i in rikaido_list:
        if i < x:
            flg = False
            break
    if flg:
        ret = min(ret,cost)

from math import isinf
if isinf(ret):
    print(-1)
else:
    print(ret)

Submission status: Accepted

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

ans = 10**8
for i in range(2**N):
    c = 0
    skill = [0]*M
    for j in range(N):
        if ( (i>>j) & 1 ):
            c += K[j][0]
            for k in range(1,M+1):
                skill[k-1] += K[j][k]
    skill.sort()
    if skill[0] >= X:
        ans = min(c,ans)

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

Submission status: Accepted

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

L = []
for _ in range(N):
  x = input().split()
  x = [int(y) for y in x]
  L.append(x)
  
cost = []

for i in range(2**N):
    list = []
    point = [0 for _ in range(M)]
    c = 0
    for j in range(N):
        if ((i >> j)&1):
            list.append(L[j])
    for x in list:
        c +=x[0]
        for i in range(1,M+1):
            point[i-1] += x[i]
    if min(point) >= X:
        cost.append(c)

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

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
N=1<<n
C=[]
A=[0 for i in range(n)]
for i in range(n):
    tmpc,*tmpa=map(int,input().split())
    C.append(tmpc)
    tmpa=np.array(tmpa,dtype=np.int64)
    A[i]=tmpa

ans=10**9
for bit in range(N):
    comp=np.zeros(m,dtype=np.int64)
    tmpans=0
    for i in range(n):
        if bit&(1<<i):
            comp+=A[i]
            tmpans+=C[i]
    flag=True
    for i in range(m):
        if comp[i]<x:
            flag=False
    if flag:
        ans=min(ans,tmpans)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
c=[]
a=[]
for _ in range(n):
  ca=list(map(int,input().split()))
  c.append(ca[0])
  a.append(ca[1:])
ans=13*pow(10,5)
for i in range(2**n):
  rikai=[0]*m
  kin=0
  for j in range(n):
    if ((i>>j) & 1):#立っているビットのところで処理が走る
      for k in range(m):
        rikai[k]+=a[j][k]
      kin+=c[j]
  if min(rikai)>=x:
    ans=min(ans,kin)
print(ans if ans<13*pow(10,5) else -1)

Submission status: Accepted

Solution code:
from itertools import product
N, M, X = map(int, input().split())
C = [0] * N
A = [[0] * M for _ in range(N)]
for i in range(N):
    c = list(map(int, input().split()))
    C[i] = c[0]
    A[i] = c[1:]

def calc(p):
    ret = 0
    cnt = [0] * M
    for i, v in enumerate(p):
        if v == 1:
            for ia, a in enumerate(A[i]):
                cnt[ia] += a
            ret += C[i]
    return ret if all(i >= X for i in cnt) else 10 ** 30
    

ans = 10 ** 30
for p in product(range(2), repeat=N):
    ans = min(ans, calc(p))

print(ans if ans < 10 ** 30 else -1)

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = f_inf
    for pattern in product([0, 1], repeat=n):
        A = [0 for _ in range(m)]
        cost = 0
        for idx, p in enumerate(pattern):
            if p == 1:
                cost += C[idx][0]
                for i in range(m):
                    A[i] += C[idx][i + 1]

        for a in A:
            if a < x:
                break
        else:
            res = min(res, cost)

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


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)]
ans = float('inf')
for bit in range(2**N):
    temp = [0]*M
    money = 0
    for i in range(N):
        if bit & (1<<i):
            money += ca[i][0]
            for idx,rikai in enumerate(ca[i][1:]):
                temp[idx] += rikai
            #temp[i] += ca[i][1+idx]
    ok = True
    for x in temp:
        if x < X:
            ok = False
    #print(bin(bit),temp)
    if ok:
        ans = min(ans,money)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,zz = [int(x) for x in input().split()]
li = []
for _ in range(n):
    z = [int(x) for x in input().split()]
    li.append(z)
ans = 10**10
for i in range(2**n):
    y = [0]*m
    num = 0
    for j in range(n):
        if (i&(1<<j)):
            for k in range(m):
                y[k]+=li[j][k+1]
            num+=li[j][0]
    if min(y)>=zz:
        ans = min(ans,num)
if ans==10**10:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:

def solve(N, M, X, books):
    ans = 10 ** 10
    f = "{:0" + str(N) + "b}"
    for k in range(2 ** N):
        cost = 0
        bins = f.format(k)
        powers = [0 for _ in range(M)]
        for i, b in enumerate(bins):
            if b == "1":
                cost += books[i][0]
                for m in range(M):
                    powers[m] += books[i][1][m]

        if all(p >= X for p in powers):
            ans = min(ans, cost)

    if ans == 10 ** 10:
        return -1
    return ans


if __name__ == "__main__":
    N, M, X = tuple(map(int, input().split(" ")))
    books = []
    for _ in range(N):
        k = list(map(int, input().split(" ")))
        books.append((k[0], k[1:]))
    print(solve(N, M, X, books))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,m,x = na()
    cs = []
    As = []
    for _ in range(n):
        ca = na()
        cs.append(ca[0])
        As.append(ca[1:])
    ans = -1
    for i in range(pow(2,n)):
        rikais = [0 for _ in range(m)]
        money = 0
        for j in range(n):
            if ((i>>j) & 1):
                money += cs[j]
                for k in range(m):
                    rikais[k] += As[j][k]
        flag = 1
        for l in range(m):
            if rikais[l] < x:
                flag = 0
                break
        if flag:
            if ans == -1:
                ans = money
            else:
                ans = min(ans,money)
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
n, m, X = map(int, input().split())
ca = [tuple(map(int, input().split()))for _ in range(n)]
INF = 10**18
ans = INF
for x in product([0, 1], repeat=n):
    cost = 0
    ms = [0]*m
    for i in range(n):
        if x[i] == 0:
            continue
        c, *a = ca[i]
        cost += c
        for j in range(m):
            ms[j] += a[j]

    if all(X <= y for y in ms) and cost < ans:
        ans = cost


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

Submission status: Accepted

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

# rについて表裏のすべての組み合わせを調べる。
ans = 10 ** 19
for b in range(2 ** n):
  aa = [0] * m
  amn = 0
  for i in range(n):
    if (b >> i) & 1:
      amn += CA[i][0]
      for k in range(m):
        aa[k] += CA[i][k + 1]
  if all(a >= x for a in aa):
    ans = min(ans, amn)  

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

Submission status: Accepted

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

    ans = float('inf')
    for i in range(1<<N):
        score = [0] * M
        tmp = []
        money = 0
        for j in range(N):
            if (i >> j) & 1:
                tmp.append(j)
                money += C[j]
        
        for t in tmp:
            for k in range(len(A[t])):
                score[k] += A[t][k]
        flag = True
        for s in score:
            if s < X:
                flag = False

        if flag:
            ans = min(ans, money)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

A = []
C = []

for i in range(N):
    a = list(map(int, input().split()))
    C.append(a[0])
    A.append(a[1:])
flag = False
ans = 12 * 10**6
for i in range(2**N):
    s = 0
    rikai = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            s += C[j]
            for k in range(M):
                rikai[k] += A[j][k]

        if (len([x for x in rikai if x >= X])) == M:
            flag = True
            ans = min(ans, s)

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

Submission status: Accepted

Solution code:
# @author 

import sys

class CSkillUp:
    def solve(self, tc=0):
        n, m, x = [int(_) for _ in input().split()]
        a = []
        c = []
        for _ in range(n):
            ci, *line = [int(_) for _ in input().split()]
            a.append(line)
            c.append(ci)

        min_cost = float('inf')
        for mask in range(2 ** n):
            und = [0] * m
            cost = 0
            for i in range(n):
                if (mask >> i) & 1:
                    cost += c[i]
                    for j in range(m):
                        und[j] += a[i][j]

            if min(und) >= x and cost < min_cost:
                min_cost = cost

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




solver = CSkillUp()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
import itertools

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

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

minmoney = -1
for use in itertools.product([0, 1], repeat=n):
    for j in range(m):
        if sum([a[i][j]*use[i] for i in range(n)]) < x:
            break
    else:
        money = sum([c[i]*use[i] for i in range(n)])
        if minmoney == -1:
            minmoney = money
        else:
            minmoney = min(minmoney, money)

print(minmoney)

Submission status: Accepted

Solution code:
n, m, x = map(int,input().split())
books = []
for _ in range(n):
    books.append(list(map(int,input().split())))
price = float('inf')

for i in range(2**n):
    prtmp = 0
    skill = [0] * m
    for j in range(n):
        if i >> j & 1:
            prtmp += books[j][0]
            for s in range(m):
                skill[s] += books[j][s+1]
    clear = True
    for s in skill:
        if s < x:
            clear = False
            break
    if clear:
        price = min(price,prtmp)

print(-1 if price == float('inf') else price)

Submission status: Accepted

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


def solve(N, M, X, C, A):
    from itertools import product, compress
    ans = float('inf')
    for selectors in product([0, 1], repeat=N):
        cost = sum(compress(C, selectors), 0)
        x = [0] * M
        for a in compress(A, selectors):
            for i, aa in enumerate(a):
                x[i] += aa
        if all(xx >= X for xx in x):
            ans = min(ans, cost)
    return -1 if ans == float('inf') else ans

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    N, M, X = list(map(int, input().split()))
    C, A = [], []
    for _ in range(N):
        c, *a = map(int, input().split())
        C.append(c)
        A.append(a)
    print(solve(N, M, X, C, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

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

B = 2**N
ans = float('inf')
for i in range(B):
    cnt = [0]*M
    flag = 1
    kane = 0
    for j in range(N):
        if i & 1 << j:
            kane += CA[j][0]
            for k in range(M):
                cnt[k] += CA[j][k+1]
    #print(i, cnt)
    for k in range(M):
        if cnt[k] < X:
            flag = 0
            break
    if flag:
        ans = min(ans, kane)
if ans == float('inf'):
    print(-1)
    exit()
print(ans)

Submission status: Accepted

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

inf = 10 ** 20
ans = inf
for bit in range(2**n):
    yen = 0
    x = [0] * m
    for i in range(n):
        if bit >> i & 1 == 1:
            for j in range(m):
                x[j] += A[i][j]
            yen += C[i]
    if all(i >= X for i in x) and ans > yen:
        ans = yen
if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
N, M, X = [int(x) for x in input().split()]
CA = []
f = False
ans = 10**9
for _ in range(N):
    lst = [int(x) for x in input().split()]
    CA.append(lst)
for i in range(2**N):
    tmp = [0] * M
    c = 0
    for j in range(N):
        if ((i >> j) & 1):
            ca = CA[j]
            c += ca[0]
            for k in range(M):
                tmp[k] += ca[k+1]
    if min(tmp) >= X:
        f = True
        ans = min(ans, c)
print(ans if f else -1)

Submission status: Accepted

Solution code:
import itertools


def main():
    N, M, X = list(map(int, input().split(' ')))
    price = list()
    effect = list()
    for _ in range(N):
        data = list(map(int, input().split(' ')))
        price.append(data[0])
        effect.append(data[1:])
    INF = 10**10
    min_money = INF
    for pattern in itertools.product([0, 1], repeat=N):
        progress = [0 for _ in range(M)]
        for i in range(N):
            for j in range(M):
                progress[j] += pattern[i] * effect[i][j]
        ok = True
        for j in range(M):
            if progress[j] < X:
                ok = False
                break
        if ok:
            money = sum([p * m for p, m in zip(pattern, price)])
            if money < min_money:
                min_money = money
    if min_money == INF:
        print(-1)
    else:
        print(min_money)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 10 ** 10
for bb in itertools.product([0, 1], repeat = n):
	comp = [0 for _ in range(m)]
	price = 0
	for i in range(n):
		if bb[i] == 1:
			for j in range(m):
				comp[j] += books[i][j + 1]
			price += books[i][0]
	if len([y for y in comp if y < x]) == 0:
		ans = min(ans, price)
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 = [[]] * n
for i in range(n):
    l = list(map(int,input().split()))
    c[i] = l[0]
    a[i] = l[1:]

inf = 10 ** 10
money = inf
for i in range(2**n):
    temp = 0
    r = [0] * m
    for j in range(n):
        if (i>>j)&1:
            temp += c[j]
            for k in range(m):
                r[k] += a[j][k]

    for j in r:
        if j >= x:continue
        break
    else:
        money = temp if temp < money else money

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

Submission status: Accepted

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

ans=10**9
for i in range(2**n):
  t_ans=0
  us=[0 for q in range(m)]
  for j in range(n):
    if (i>>j)&1:
      use=l[j]
      t_ans+=use[0]
      for w in range(m):
        us[w]+=use[w+1]
  check=1
  for z in us:
    if z<x:
      check=0
  if check==1:
    ans=min(ans,t_ans)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
ans = 100000000
for i in range(2**N):
    n = i
    al = [0] * M
    pr = 0
    for j in range(N):
        if n % 2 == 1:
            pr += A[j][0]
            for k in range(M):
                al[k] += A[j][k+1]
        n //= 2
    tes = 0
    for j in range(M):
        if al[j] < X:
            tes = 1

    if tes == 0:
        ans = min([ans, pr])

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

Submission status: Accepted

Solution code:
INF = 10 ** 12
def main():
    N, M, X = (int(_) for _ in input().split())
    C = [[int(_) for _ in input().split()] for _ in range(N)]
    out = INF
    for bit in range(1<<N):
        rikai = [0] * M
        cc = 0
        for i in range(N):
            if (bit >> i) & 1:
                cc += C[i][0]
                for j in range(1, M+1):
                    rikai[j-1] += C[i][j]
        if all([rikai[i] >= X for i in range(M)]):
            out = min(out, cc)
    print(out if out != INF else -1)
    return
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 10 ** 7
for i in range(2**n):
    money = 0
    a = [0] * m
    for j in range(n):
        if i >> j & 1:
            money += y[j][0]
            a = [a[k] + y[j][k+1] for k in range(m)]
    flag = True
    for j in a:
        if j < x:
            flag = False
    if flag:
        ans = min(ans, money)

if ans < 10 ** 7:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools

N,M,X = map(int,input().split())
COST = [0]*N
POWER = [0]*N
for i in range(N):
    AAA = list(map(int,input().split()))
    COST[i] = AAA[0]
    POWER[i] = AAA[1:]

INF = 10**10
ans = INF

for Q in itertools.product((0,1),repeat=N):
    c = 0
    p = [0]*M
    for k,v in enumerate(Q):
        if v == 0:
            continue
        c += COST[k]
        for kk,vv in enumerate(POWER[k]):
            p[kk] += vv
        b = True
        for i in range(M):
            if p[i] < X:
                b = False
                break
        if b:
            ans = min(ans,c)

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

Submission status: Accepted

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

# 全探索
ans = []
for i in range(2 ** n):
    num = [0] * m
    expense = 0
    for j in range(n):
        if i % 2 == 0:
            expense += c[j]
            for k in range(m):
                num[k] += a[j][k]
        i //= 2
    
    for j in num:
        if j < x:
            break
    else:
        ans.append(expense)

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

a = [sum(l) for l in zip(*A)]
if any(X > x for x in a):
    print(-1)
    exit(0)


ans = 1e18
for i in range(2 ** N):
    c = 0
    a = [0] * M
    price = 0
    for j in range(N):
        if (i >> j) & 1:
            price += C[j]
            for k in range(M):
                a[k] += A[j][k]
    if all(v >= X for v in a):
        ans = min(ans, price)

print(ans)

Submission status: Accepted

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    n,m,x=L()
    understand=[0]*m
    book=[[0]*m for i in range(n)]
    price=[]*m
    for i in range(n):
        tmp=L()
        price.append(tmp[0])
        for j in range(m):
            book[i][j]=tmp[j+1]
    ans=1e+12
    for bit in range(1<<n):
        sum=0
        understand=[0]*m
        for i in range(n):
            if bit&(1<<i):
                sum+=price[i]
                for j in range(m):
                    understand[j]+=book[i][j]
        flag=True
        for i in range(m):
            if understand[i]<x:
                flag=False
        if flag:
            ans=min(ans,sum)
    if ans==1e+12:
        ans=-1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ans=10**9
from itertools import combinations as co
l=[list(map(int,input().split())) for _ in range(n)]
for i in range(1,n+1):
  for ch in co(range(n),i):
    f=1
    t=[0]*m
    s=0
    for j in ch:
      s+=l[j][0]
      for k in range(1,m+1):
        t[k-1]+=l[j][k]
    for test in t:
      if test<x:
        f=0
        break
    if f:
      ans=min(ans,s)
if ans==10**9:
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def check(l):
  for i in l:
    if i >= X:
      continue
    else:
      return False
  else:
    return True

N,M,X = IL()
ca = [IL() for i in range(N)]

ans = MAX_INT
for i in range(1 << N):
  x = 0
  rikaido = [0]*M
  for j in range(N):
    if (i >> j) & 1 == 1:
      x += ca[j][0]
      for k in range(1,M+1):
        rikaido[k-1] += ca[j][k]
  else:
    if check(rikaido):
      ans = min(ans, x)
if ans == MAX_INT:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
from itertools import product


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

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

ans = sum(c) + 10
for choose in product([0, 1], repeat=n):
	# print(choose)
	cost = 0
	good = True
	book = 0
	while good and book < m:
		sum_got = 0
		for buys in range(n):
			if choose[buys] == 1:
				sum_got += a[buys][book]
		# print("sum_got", sum_got)
		if sum_got < x:
			good = False
			break
		book += 1

	if good:
		for buys in range(n):
			if choose[buys] == 1:
				cost += c[buys]
		# print("cost", cost)
		if cost < ans:
			ans = cost
if ans != sum(c) + 10:
	print(ans)
else:
	print(-1)