Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

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

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

def tobin(x,n):
    return format(x,'b').zfill(n)

ans = 1e10
for i in range(2**n):
    b = format(i,'b').zfill(n)
    # print(b)
    buf = [0 for i in range(m)]
    temp = 0
    for j in range(n):
        if b[j]=="1":
            temp += books[j][0]
            for k in range(1,m+1):
                buf[k-1] += books[j][k]
        else:
            continue
    # print(buf)
    flag = True
    for val in buf:
        if val < x:
            flag = False

    if flag and ans > temp:
        ans = temp
    else:
        continue

if ans > 1e9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
c=[]
A=[]
for _ in range(n):
    l = [int(i) for i in input().split()]
    c.append(l[0])
    A.append(l[1:])
c=np.array(c)
A=np.array(A)
ans = 20*10**9
bits =[]

for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1): 
            bag.append(j)
    ar = np.sum(A[bag],axis=0)
    if all(ar>=x):
        temp = np.sum(c[bag])
        ans = min(ans,temp)
if ans == 20*10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ans = float('inf')
for n in range(2**N):
    a = [0]*M
    c = 0
    for i in range(N):
        if n&(2**i)==2**i:
            for j in range(M):
                a[j] += A[i][j]
            c += C[i]
    f = True
    for i in range(M):
        if a[i] < X:
            f = False
    if f:
        ans = min(ans,c)

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m, x = map(int, input().split())
    c = [None for _ in range(n)]
    a = [None for _ in range(n)]
    for i in range(n):
        p = list(map(int, input().split()))
        c[i] = p[0]
        a[i] = p[1:m+1]

    ans = 10 ** 18
    for i in range(1 << n):
        mask = [False for _ in range(n)]
        p = i
        q = 0
        while p > 0:
            if p & 1:
                mask[q] = True
            p = p >> 1
            q += 1
        skill = [0 for _ in range(m)]
        cost = 0
        for j in range(n):
            if mask[j]:
                for k in range(m):
                    skill[k] += a[j][k]
                cost += c[j]
        good = True
        for j in range(m):
            if skill[j] < x:
                good = False
                break
        if good and cost < ans:
            ans = cost

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, m, x = map(int, input().split())
c = [0] * n
a = [[0] * m for _ in range(n)]
for i in range(n):
    c[i], *t = list(map(int, input().split()))
    a[i] = t
ans = 10 ** 9
for b in range(1 << n):
    s = 0
    li = [0] * m
    for i in range(n):
        if ~b >> i & 1:
            continue
        s += c[i]
        for j in range(m):
            li[j] += a[i][j]
    if any(y < x for y in li):
        continue
    ans = min(ans, s)
print(ans if ans < 10 ** 9 else -1)

Submission status: Accepted

Solution code:
#!python3

import numpy as np


def LI():
    return list(map(int, input().split()))

# input
N, M, X = LI()
CA = np.array([LI() for _ in range(N)])

INF = 10 ** 15


def main():
    n = 2 ** N
    ans = INF
    for i in range(1, n):
        b = format(i, "0{}b".format(N))
        c = 0
        l = np.zeros(M)
        for j in range(N):
            if b[j] == "1":
                c += CA[j][0]
                l += CA[j][1:]
        if (l >= X).all():
            ans = min(ans, c)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M,X=MI()
    A=[[] for _ in range(N)]
    C=[0]*N
    for i in range(N):
        c,*a = MI()
        A[i] = a
        C[i] = c

    def f(mask):
        B = [0]*M
        cost = 0

        for i in range(N):
            if mask >> i & 1:
                cost += C[i]
                for j,a in enumerate(A[i]):
                    B[j] += a

        ok = True
        for b in B:
            if(b<X):
                ok = False
        return ok,cost

    ans = inf
    for mask in range(1<<N):
        ok,cost = f(mask)
        if(ok):
            ans = min(ans, cost)
    if(ans == inf):
        print(-1)
    else:
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [-1] * N
A = [[] for _ in range(N)]
for i in range(N):
    C[i], *A[i] = map(int, input().split())
ans = 10 ** 10
for p in range(1 << N):
    R = [0] * M
    c = 0
    for i in range(N):
        if p & (1 << i):
            c += C[i]
            for j in range(M):
                R[j] += A[i][j]
    for j in range(M):
        if R[j] < X: break
    else:
        ans = min(ans, c)
print(ans if ans != 10 ** 10 else -1)

Submission status: Accepted

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

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

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

C = [ca[0] for ca in CA]
A = [ca[1:] for ca in CA]

ans = INF
for i in range(2 ** N):
    cnt = [0] * M
    tmp = 0
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                cnt[k] += A[j][k]
            tmp += C[j]
    flag = 1
    for k in range(M):
        if cnt[k] < X:
            flag = 0
            break
    if flag:
        ans = min(ans, tmp)
        
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
ans=float("inf")
for i in range(2**n):
    ll=[0 for _ in range(m+1)]
    now=0
    for j in range(n):
        if (i>>j)&1:
            now+=l[j][0]
            for k in range(m):
                ll[k+1]+=l[j][1+k]
    if all(ll[s]>=x for s in range(1,m+1)):
        ans=min(ans,now)
print(ans if ans!=float("inf") else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
l = []
for i in range(n):
    tmp = list(map(int,input().split()))
    l.append([tmp[0], tmp[1:]])
res = 10 ** 100
for i in range(1 << n):
    mon = 0
    recog = [0] * m
    for j in range(n):
        if i & (1 << j):
            a,b = l[j]
            mon += a
            for k in range(m):
                recog[k] += b[k]
    if all(i >= x for i in recog):
        res = min(res, mon)
if res == 10 ** 100:
    res = -1
print(res)

Submission status: Accepted

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

ans = 10 ** 18
for bit_state in range(1 << n):
    tmp = [0] * m
    cost = 0
    for i in range(n):
        if bit_state & (1 << i):
            for j in range(m):
                tmp[j] += info[i][j + 1]
            cost += info[i][0]
    flag = True
    for j in range(m):
        if tmp[j] < x:
            flag = False
    if flag:
        ans = min(cost, ans)
        
        
if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

# print(c)
# print(*a, sep='\n')

ans = sum(c) + 1
for bit in range(1 << n):
    cand = 0
    b = [0] * m
    for i in range(n):
        if (bit >> i) & 1:
            cand += c[i]
            for j in range(m):
                b[j] += a[i][j]

    is_possible = True
    for j in range(m):
        if b[j] < x:
            is_possible = False
            break

    if is_possible:
        ans = min(ans, cand)

if ans == sum(c) + 1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def sol(ans, case):
    points = [0 for _ in range(M)]
    tmp_cost = 0
    for i, flag in enumerate(case):
        if flag == '1':
            for j in range(M):
                points[j] += A[i][j]
            tmp_cost += C[i]

    for point in points:
        if point < X:
            return float('inf')
    return tmp_cost


if __name__ == '__main__':
    N, M, X = map(int, input().split())
    C = []
    A = []
    for _ in range(N):
        tmp_input = list(map(int, input().split()))
        C.append(tmp_input[0])
        A.append(tmp_input[1:])

    ans = float('inf')
    for i in range(2 ** N):
        case = bin(i)[2:].zfill(N)
        ans = min(ans, sol(ans, case))

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, x = LI()
L = []
C = []
for _ in range(n):
    c, *A = LI()
    C += [c]
    L += [A]

ans = INF

for i in range(2 ** n):
    B = [0] * m
    ret = 0
    for j in range(n):
        if i >> j & 1:
            ret += C[j]
            for k in range(m):
                B[k] += L[j][k]
    for b in B:
        if b < x:
            break
    else:
        ans = min(ans, ret)

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

Submission status: Accepted

Solution code:
N, M, C = map(int, input().split())
R = 10**18
X = []
for _ in range(N):
    X.append(list(map(int, input().split())))
for i in range(2**N):
    c = 0
    Y = [0] * M
    ct = 0
    for _ in range(N):
        if i%2:
            cc, y = X[c][0], X[c][1:]
            for j in range(M):
                Y[j] += y[j]
            ct += cc
        c += 1
        i = i//2
        for j in range(M):
            if Y[j] < C:
                break
        else:
            R = min(ct, R)
if R < 10**18:
    print(R)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Clist = []
Alist = []
for i in range(N):
    C, *A = map(int, input().split())
    Clist.append(C)
    Alist.append(list(A))
ans = []
for i in range(2**N):
    money = 0
    rikai = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            money += Clist[j]
            for k in range(M):
                rikai[k] += Alist[j][k]
    if all([r>=X for r in rikai]):
        ans.append(money)
if ans:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

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

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

INF = 10**18
ans = INF
for bit in range(1<<N):
    cost = 0
    Get = [0]*M
    for i in range(N):
        if bit&(1<<i):
            cost += C[i]
            for m in range(M):
                Get[m] += As[i][m]
    ok = True
    for m in range(M):
        if Get[m] < X:
            ok = False
            break
    if ok:
        ans = min(ans, cost)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n, m, x = map(int, input().split())
book = []
for _ in range(n):
    info = [int(item) for item in input().split()]
    book.append(info)

ans = 10**10
for i in range(2**n):
    understanding = [0] * m
    cost = 0
    for j in range(n):
        if i & 1 << j:
            cost += book[j][0]
            for k in range(1, m+1):
                understanding[k-1] += book[j][k]
    ok = True
    for und in understanding:
        if und < x: 
            ok = False
            break
    if ok:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
MOD = 10**9+7
# MOD = 998244353

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

min_val = float("inf")
for i in range(1<<n):
    hon = [0]*m
    val = 0
    for j in range(n):
        if (i>>j) & 1:
            val += A[j][0]
            for k in range(m):
                hon[k] += A[j][k+1]

    if all([hon[t] >= x for t in range(m)]):
        min_val = min(min_val, val)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
B=[]
for i in range(n):
    B.append(list(map(int,input().split())))
    
ans=10**9
for i in range(2**n):
    A=[0]*m
    cnt=0
    for j in range(n):
        if i>>j&1:
            cnt+=B[j][0]
            for k in range(m):
                A[k]+=B[j][k+1]
    if min(A)>=x:
        ans=min(cnt,ans)
if ans==10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

books = tuple(tuple(map(int,input().split())) for _ in range(N))

def it():
    for choice in product(range(2),repeat=N):
        cost = 0
        skills = [0]*M
        for flag,book in zip(choice,books):
            if flag:
                C, A = book[0], book[1:]
                cost += C
                for i,a in enumerate(A):
                    skills[i] += a

        if all(v >= X for v in skills):
            yield cost

best = min(it(), default=None)
print(-1 if best is None else best)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for i in range(n)]
ans = 1e18
for i in range(1<<n):
    cost = 0
    udst = [0] * m
    for j in range(n):
        if((i>>j)&1):
            cost += ca[j][0]
            for k in range(m):
                udst[k] += ca[j][k+1]
    ok = True
    for j in range(m):
        if udst[j]<x: ok = False
    if ok: ans = min(ans, cost)

if ans>=1e18: print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N, M, X = Scanner.map_int()
    C = [0 for _ in range(N)]
    A = [[0 for _ in range(M)]for _ in range(N)]
    for i in range(N):
        c, *K = Scanner.map_int()
        C[i] = c
        for j in range(M):
            A[i][j] = K[j]
    ans = INF
    for i in range(1 << N):
        cnt = 0
        T = [0 for _ in range(M)]
        for j in range(N):
            if i >> j & 1:
                for k in range(M):
                    T[k] += A[j][k]
                cnt += C[j]
        if min(T) >= X:
            ans = min(ans, cnt)
    if ans == INF:
        print(-1)
    else:
        print(ans)


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
from itertools import combinations_with_replacement

n,m,x=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
ans=2<<32

for bit in range(2**n):
    now=bin(bit)[2:].zfill(n)[::-1]
    pricesum=0
    unds=[0]*m
    for i in range(n):
        if now[i]!="1":
            continue
        pricesum+=a[i][0]
        for j in range(m):
            unds[j]+=a[i][j+1]
    if min(unds)>=x:
        ans=min(ans,pricesum)

print(-1 if ans==2<<32 else ans)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, M, X = map(int, input().split())
    C = [[int(c) for c in input().split()] for _ in range(N)]
    minCost = 10 ** 20
    for i in range(2 ** N):
        cost = 0
        S = [0] * M
        d = i
        for j in range(N):
            if d % 2 == 1:
                cost += C[j][0]
                for k in range(M): S[k] += C[j][k + 1]
            d //= 2
        for s in S:
            if s < X: break
        else: minCost = min(minCost, cost)
    if minCost == 10 ** 20: print(-1)
    else: print(minCost)

    return  0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    T = SI()
    if S==T[:len(S)]:
        if len(S)+1==len(T):
            print("Yes")
            return
    print("No")
    return

def examB():
    A, B, C, K = LI()
    ans = 0
    if A>=K:
        ans = K
    else:
        ans += A
        K -= A
        if K>B:
            K -= B
            ans -= K
    print(ans)
    return

def examC():
    N, M, X = LI()
    C = [LI()for _ in range(N)]
    loop = 2**N
    ans = inf
    for l in range(loop):
        cur = 0
        A = [0]*M
        for j in range(N):
            if (1<<j)&l>0:
                cur += C[j][0]
                for k in range(M):
                    A[k] += C[j][k+1]
        flag = True
        for i in range(M):
            if A[i]<X:
                flag = False
                break
        if flag:
            ans = min(ans,cur)
    if ans==inf:
        print(-1)
        return
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M, X = getlist()
	L = []
	for i in range(N):
		CA = getlist()
		L.append(CA)

	ans = INF
	for i in range(1 << N):
		money = 0
		algo = [0] * M
		for j in range(N):
			if ((i >> j) & 1) == 1:
				money += L[j][0]
				for k in range(M):
					algo[k] += L[j][k + 1]

		judge = "Yes"
		for j in range(M):
			if algo[j] < X:
				judge = "No"

		if judge == "Yes":
			ans = min(ans, money)

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


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, M, X = [int(x) for x in input().split()]
    CA = [[int(x) for x in input().split()] for _ in range(N)]

    ans = float("inf")
    for i in range(2 ** N):
        a = [0] * M
        anstmp = 0
        for j in range(N):
            if i >> j & 1:
                anstmp += CA[j][0]
                for k in range(1, M + 1):
                    a[k - 1] += CA[j][k]

        for aa in a:
            if aa < X:
                break
        else:
            ans = min(ans, anstmp)

    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())
l = [None] * n
c = [0] * n
for i in range(n):
    cs, *a = map(int, input().split())
    l[i] = a
    c[i] = cs
ans = float('inf')
for i in range(1 << n):
    t = [0] * m
    cs = 0
    for j in range(n):
        if (i >> j) & 1:
            cs += c[j]
            for k in range(m):
                t[k] += l[j][k]
    for k in t:
        if k < x:
            break
    else:
        ans = min(ans, cs)
if ans == float('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 i in range(n)]
ans=float("INF")
for i in range(2**n):
    var=[a for a in range(n) if (i>>a)%2]
    now=[0]*m

    y=0
    for j in var:
        y+=l[j][0]
        for h in range(m):
            now[h]+=l[j][h+1]
    if min(now)>=x:ans=min(ans,y)
print(ans) if ans!=float("INF") else print(-1)

Submission status: Accepted

Solution code:
from itertools import *

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

res = 10**9
for s in product([0, 1], repeat = n):
    u = [0 for i in range(m)]
    cost = 0
    for i, b in enumerate(s):
        if b == 0: continue
        cost += c[i]
        for j in range(m):
            u[j] += a[i][j]
    if min(u) >= x:
        res = min(res, cost)
      
if res == 10**9: res = -1
print(res)

Submission status: Accepted

Solution code:
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:])

ans=float('inf')

for bit in range(1<<N):
    ML=[0]*M
    cost=0
    for i in range(N):
        if bit>>i & 1 == 1:
            cost+=C[i]
            for j in range(M):
                ML[j]+=A[i][j]
    if all(m>=X for m in ML):
        ans=min(ans,cost)
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

# from abc118_B.py

def solve(n, m, x, c, a):
    ret = float('inf')
    N = 1 << 12
    for b in range(N):
        tmp = [0] * m
        C = 0
        for i in range(n):
            if b & (1 << i) > 0:
                C += c[i]
                for j, aa in enumerate(a[i]):
                    tmp[j] += aa
        found = True
        for j in range(m):
            if tmp[j] < x:
                found = False
                break
        if found:
            ret = min(ret, C)
    if ret == float('inf'):
        ret = -1
    print(ret)
    return

def main():
    n, m, x = map(int, input().split())
    c = []
    a = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        c.append(tmp[0])
        a.append(tmp[1:])
    solve(n, m, x, c, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

inf = 10**10
ans = inf
for i in range(2**n):
    und = [0] * m
    cost = 0
    for j in range(n):
        if((i>>j)&1):
            cost += ca[j][0]
            for k in range(m):
                und[k] += ca[j][k+1]
    if(min(und) >= x):
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
ls = [list(map(int, input().split())) for i in range(n)]
ans=1001001001001
for i in range(1 << n):
    u=[0]*m
    cost=0
    for j in range(n):
        if i & 1 << j:
            for k in range(1,m+1):
                u[k-1] += ls[j][k]
            cost += ls[j][0]
    for k in range(m):
        if u[k] < x:
            break
    else:
        ans = min(ans,cost)

if ans == 1001001001001:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
CA = [list(map(int,input().split())) for _ in [0]*N]

INF = 10**5*100
ans = INF
for i in range(2**N):
    tmp = 0
    B = [0]*M
    for j in range(N):
        if i>>j&1==0 : continue
        tmp += CA[j][0]
        for k,a in enumerate(CA[j][1:]):
            B[k] += a
    if min(B)>=X:
        ans = min(ans,tmp)
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

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

inf = 10 ** 20
mi = inf

for i in range(1 << N):
  L = [0] * M
  c = 0
  for j in range(N):
    t = i & (1 << j)
    if t == 0: continue
    c += CA[j][0]
    for k in range(M):
      L[k] += CA[j][k + 1]
  for j in L:
    if j < X: break
  else:
    mi = min(mi, c)

if mi == inf:
  print(-1)
else:
  print(mi)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
dp = []
dp.append([[0] * m,0])
for i in range(n):
    next = []
    lis = list(map(int,input().split()))
    cost = lis[0]
    lis = lis[1:]
    for li,cos in dp:
        next.append([li,cos])
        co = [0] * m
  #         print(len(co),len(li),len(lis))
        for j in range(m):
            co[j] = li[j] + lis[j]
        next.append([co,cos+cost])
    dp = next
  #     print(dp)
ans = 10 ** 100
  # print(dp)
for li,cos in dp:
    if min(li) >= k:
        ans = min(ans,cos)
if ans == 10 ** 100:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N,M,X = Ints()
C = []
A = []

for i in range(N):
    In = IntList()
    C.append(In[0])
    A.append(In[1:])
    
ans = 10**16

import itertools

for i in itertools.product([0,1], repeat=N):
    Now = [0]*M
    tmpans = 0
    for j in range(N):
        if i[j]==1:
            tmpans += C[j]
            for k in range(M):
                Now[k] += A[j][k]
    if min(Now) >= X:
        ans = min(ans,tmpans)
        
if ans==10**16:
    print(-1)
else:
    print(ans)