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:
def dfs(now, l):
    if now == n:
        for ll in l[1:]:
            if ll < x:
                return inf
        return l[0]
    else:
        add_l = []
        for i, j in zip(l, book[now]):
            add = i + j
            add_l.append(add)
        return min(dfs(now + 1, add_l), dfs(now + 1, l))


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

book = []
su = 0
for i in range(n):
    tmp = list(map(int, input().split()))
    su += tmp[0]
    book.append(tmp)

first = [0 for _ in range(m + 1)]
ans = dfs(0, first)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
B = [list(map(int,input().split())) for _ in range(n)]
ans = 10**9

for i in range(2**n):
    R = [0 for _ in range(m)]
    tmp = 0
    for j in range(n):
        if i & (1 << j):
            tmp += B[j][0]
            for k,b in enumerate(B[j][1:]):
                R[k] += b
    flag = True
    for r in R:
        if r < x:
            flag = False
            break
    if flag:
        ans = min(ans,tmp)
if ans == 10**9:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def print_ans(B):
    for b in B:
        b.sort(key=lambda l: int(l))
        print(" ".join(b))



def main():
    N, M, X = read_values()
    A = read_lists(N)

    res = V(min)
    for i in range(2 ** N):
        K = [0] * (M + 1)
        for n in range(N):
            if i & (1 << n):
                for k in range(M + 1):
                    K[k] += A[n][k]
                
                for k in range(1, M + 1):
                    if K[k] < X:
                        break
                else:
                    res.ud(K[0])

    if res.v is None:
        print(-1)
    else:
        print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
## coding: UTF-8
from itertools import product
import sys

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

#print(N, M, X, lc)

combi = list(product('YN', repeat = N))
#print(combi)


able = 'No'
ans = sys.maxsize
#print(ans)

for i in range(len(combi)):
    #print(combi[i])
    money = 0
    lx = [0] * M
    for j in range(N):
        #print(combi[i][j])
        if(combi[i][j] == 'Y'):
            money += lc[j][0]
            for k in range(M):
                lx[k] += lc[j][k+1]
    #print(money, lx)
    if(min(lx) >= X):
        #print('OK')
        able = 'Yes'
        ans = min(ans, money)
    #print(able, ans)

if(able == 'No'):
    print(-1)
else:
    print(ans)

'''
for i in range(len(combi)):
    print(combi[i])
    money = 0
    lx = [0] * M
    for j in range(M):
        if(combi[i][j] == 'Y'):
            money += lc[i][0]
            for k in range(M):
                lx[k] += lc[i][k+1]
            print(money, lx)
'''

Submission status: Accepted

Solution code:
import itertools

n, m ,x = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
ans = 10**10

for i in itertools.product([0,1], repeat=n):
    c = 0
    b = [0]*m
    for j in range(n):
        if i[j] == 1:
            c += a[j][0]
            for k in range(m):
                b[k] += a[j][k+1]
    for l in range(m):
        if b[l] < x:
            break
    else:
        ans = min(ans, c)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ans = []
def read(n,last,*under):
    if n == 0:
        ans.append(list(under))
    else:
        for i in range(last+1, N):
            ui = list(under)
            for m in range(M+1):
                ui[m] += data[i][m]
            read(n-1,i,*ui)

for n in range(1,N+1):
    read(n,-1,*[0]*(M+1))

ans = sorted(ans)
for item in ans:
    flag_m = True
    for m in range(1,M+1):
        if item[m] < X: flag_m = False
    if flag_m:
        print(item[0])
        break

if not flag_m: print(-1)

Submission status: Accepted

Solution code:
from sys import exit
N, M, X = map(int,input().split())
CA = []
for i in range(N): CA.append(list(map(int,input().split())))
ans = 10 ** 9
for i in range(2 ** N):
    buy = []
    cost = 0
    flag = 0
    for j in range(N):
        if (i >> j) & 1:
            buy.append(CA[j])
    for i in range(M):
        if sum(skill[i + 1] for skill in buy) < X:
            flag = 1
            break
    if flag != 1:
        cost = sum(skill[0] for skill in buy)
        ans = min(ans,cost)
if ans == 10 ** 9: print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    from itertools import combinations
    n, m, x = map(int, input().split())
    l = [list(map(int, input().split())) for _ in range(n)]

    ans = 10 ** 15
    for i in range(1, n + 1):
        for comb in combinations(l, i):
            y = np.array([x for _ in range(m)])
            tmp = 0
            for p in comb:
                tmp += p[0]
                y -= np.array(p[1:])
            s = sum([j <= 0 for j in y])
            if s == m:
                ans = min(ans, tmp)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np

n, m, x = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(n)]
ans = -1
for bool_list in range(2 ** n):
    bool_list = bin(bool_list)[2:].zfill(n)
    cost = 0
    exp = np.array([0] * m)
    for i, b in enumerate(books):
        if bool_list[i] == '1': continue
        cost += b[0]
        tmp = np.array(b[1:])
        exp = exp + tmp
    for y in exp:
        if y < x: break
    else:
        if ans == -1:
            ans = cost
        else:
            ans = min(cost, ans)
print(ans)

Submission status: Accepted

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M, X = mulinputs()
    datas = []
    check = [0] * M
    for _ in range(N):
        tmp = list(mulinputs())
        datas.append(tmp)
        for i in range(1,M+1):
            check[i-1] += tmp[i]
    for c in check:
        if c < X:
            print(-1)
            exit()

    min_value = INF
    for b in range(1<<N):
        tmp = b
        total = 0
        idx = 0
        check = [0] * M
        while tmp > 0:
            if tmp%2==1:
                total += datas[idx][0]
                for m in range(1, M+1):
                    check[m-1] += datas[idx][m]
            tmp >>=1
            idx += 1
        if len(check) == len(list(filter(lambda x: x >= X, check))):
            min_value = min(total, min_value)


    # 出力
    print(min_value)

Submission status: Accepted

Solution code:
INF = float("inf")
# MOD = 10 ** 9 + 7
# import sys
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
import numpy as np


def main():
    n, m, x = map(int, input().split())
    books = [np.array(list(map(int, input().split()))) for _ in range(n)]
    ans = INF
    for bit in range(1 << n):
        bag = [0] * n
        for i in range(n):
            if bit >> i & 1:
                bag[i] = 1
        tmp = np.array([0] * m)
        cost = 0
        for i, v in enumerate(bag):
            if v:
                cost += books[i][0]
                tmp += books[i][1:]
        if all([i >= x for i in tmp]):
            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())
items = []
for _ in range(N):
    tmps = list(map(int, input().split()))
    price = tmps[0]
    l = tmps[1:]
    items.append((price, l))
n = len(items)
patterns = []

for i in range(2 ** n):
    bag = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(items[j])  # フラグが立っていたら bag に果物を詰める
    patterns.append(bag)

ans = 100000000000
for pattern in patterns:
    sum_price = 0
    sum_l = [0 for _ in range(M)]
    for price, l in pattern:
        sum_price += price
        for i in range(M):
            sum_l[i] += l[i]
    check = True
    for i in range(M):
        if sum_l[i] < X:
            check = False
    if check:
        ans = min(ans, sum_price)

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

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit
# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))

N, M, X = geta(int)
b = []
for _ in range(N):
    b.append(geta(int))

inf = 10**7

ans = inf

for c in range(0, 2**N):
    tmp = c
    cost = 0
    bi = 0
    sk = [0] * M
    while tmp > 0:
        if tmp & 1 == 1:
            cost += b[bi][0]
            for i in range(M):
                sk[i] += b[bi][i + 1]

        tmp = tmp >> 1
        bi += 1

    if min(sk) >= X and ans > cost:
        ans = cost

print(ans if ans < inf else -1)

Submission status: Accepted

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

num = 2**n
mon = 10**18

for i in range(num):
    tmp = format(i, '0'+str(n)+'b')
    #print(tmp)
    tmp_mon = 0
    alg = [0]*(m)
    for j in range(n):
        if int(tmp[j]) == 1:
            for k in range(m):
                alg[k] += ca[j][1+k]
            tmp_mon += ca[j][0]
    
    flag = True
    #print(alg,tmp_mon)
    for j in range(m):
        if alg[j] < x:
            flag = False
            break
    
    if flag == False:
        continue
    
    mon = min(tmp_mon,mon)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
matrix = tuple(tuple(map(int, input().split())) for _ in range(N))
ans = float("inf")
for comb in range(1 << N):
    temp = [0] * (M + 1)
    for i in range(N):
        if comb & (1 << i):
            for m in range(M + 1):
                temp[m] += matrix[i][m]
    if all(temp[i] >= X for i in range(1, M + 1)):
        ans = min(ans, temp[0])
print(-1 if ans == float("inf") else ans)

Submission status: Accepted

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

c = []
a = []

for i in range(n):
    ai = list(map(int,input().split()))
    ci = ai.pop(0)
    a.append(ai)
    c.append(ci)

for j in range(m):
    tmp = 0
    for i in range(n):
        tmp += a[i][j]
    if tmp<x:
        print(-1)
        exit()

def dps(lis, num):
    if num == n:
        res = 0
        for j in range(m):
            tmp = 0
            for i in lis:
                tmp += a[i][j]
            if tmp < x:
                return 10000000
        for i in lis:
            res += c[i]
        return res
    else:
        lisnext = lis + [num]
        return min(dps(lisnext,num+1),dps(lis,num+1))

print(dps([],0))

Submission status: Accepted

Solution code:
from itertools import product
n, m, x = list(map(int, input().split()))
cl = [0] * n
al = [[]*m for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    cl[i] = tmp[0]
    al[i] = tmp[1:]


def dfs(status, book):
    for i in range(m):
        status[i] += book[i]
    return status


ans = 10**10
for bit in product([0, 1], repeat=n):
    # print(bit)
    status = [0]*m
    money = 0
    for i, b in enumerate(list(bit)):
        if b == 1:
            for k in range(m):
                status[k] += al[i][k]
            money += cl[i]
    flag = True
    for i in range(m):
        if status[i] >= x:
            continue
        else:
            flag = False
    if flag:
        ans = min(ans, money)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
INF = 10**13
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    CA = list(map(int, input().split()))
    C += [CA[0]]
    A += [CA[1:]]
ans = INF
for b in range(2**N):
    tmpA = [0] * M
    cost = 0
    for i in range(N):
        if (b >> i) & 1:
            cost += C[i]
            for ii, ai in enumerate(A[i]):
                tmpA[ii] += ai
    flag = True
    for ai in tmpA:
        if ai >= X:
            continue
        flag = False
        break
    if flag:
        ans = min(ans, cost)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M, X = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]
    # print(A)
    total_cost = 1e10
    possible = False
    for i in range(2**N):
        tmp_cost = 0
        rikai = [0]*M
        for j in range(N):
            if ((i >> j) & 1):
                # print(bin(i))
                tmp_cost += A[j][0]
                for k in range(M):
                    rikai[k] += A[j][k+1]
        # print(rikai)
        if min(rikai) >= X:
            possible = True
            total_cost = min(total_cost, tmp_cost)
    
    if possible:
        print(total_cost)
    else:
        print(-1)


if __name__ == '__main__':
    main()

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]
    for j in range(m):
        a[i][j] = tmp[1 + j]

ans = float("inf")
for mask in range(1 << n):
    sum = 0
    skill = [0] * m
    for j in range(n):
        if (mask >> j) & 1 == 1:
            for k in range(m):
                skill[k] += a[j][k]
            sum += c[j]

    flag = True
    for i in range(m):
        if skill[i] < x:
            flag = False
            break

    if flag is True:
        ans = min(ans, sum)

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split(" "))
A = []
lis = []
rikai = [[0 for _ in range(M)]for _ in range(2 ** N)]
flag = True
kane = 0
ans = 10 ** 10
for i in range(N):
    A.append(list(map(int,input().split(" "))))
    
for i in range(2 ** N):
    lis.clear()
    kane = 0
    flag = True
    for i2 in range(N):
        if ((i >> i2) & 1):
            lis.append(i2)
    for i2 in lis:
        kane += A[i2][0]
        for i3 in range(M):
            rikai[i][i3] += A[i2][i3 + 1]
    for i2 in rikai[i]:
        if i2 < X:
            flag = False
    if flag:
        if ans > kane:
            ans = kane
            
if ans != 10 ** 10:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

ans=10**8
for mask in range(1,1<<n):
    mem=[0]*m
    c=0
    for i in range(n):
        if (mask & (1<<i)):
            c+=book[i+1][0]
            for j in range(m):
                mem[j]+=book[i+1][j+1]
    for j in range(m):
        if mem[j]<x:
            break
    else:
        ans=min(ans,c)
if ans==10**8:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
c = [0 for i in range(n)]
a = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    c[i] = tmp[0]
    for j in range(m):
        a[i][j] = tmp[j + 1]
able = False
ans = 10**8
for i in range(2**n):
    price = 0
    flag = True
    buy = [0 for j in range(n)]
    rikai = [0 for j in range(m)]
    for j in range(n):
        if i>>j & 1 == 1:buy[j] = 1
    for j in range(n):
        if buy[j] == 1:
            price += c[j]
            for k in range(m):
                rikai[k] += a[j][k]
    for j in range(m):
        if rikai[j] < x:
            flag = False
            break
    if not flag:continue
    able = True
    ans = min(ans,price)
if able:print(ans)
else:print(-1)

Submission status: Accepted

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

CA = []
for i in range(N):
    CA.append(list(map(int, input().split())))
    
ans = 10**10
flag = False
for i in range(2 ** N):
    purchase = [0] * N
    for j in range(N):
        if ((i >> j) & 1):
            purchase[N - 1 - j] = 1
    money = 0
    skill = [0] * M
    for j in range(N):
        if purchase[j] == 1:
            money += CA[j][0]
            for k in range(1, M+1):
                skill[k-1] += CA[j][k]
    if min(skill) >= X:
        ans = min(ans, money)
        flag = True

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

Submission status: Accepted

Solution code:
#map(int,input().split())
n,m,x = map(int,input().split())
c=[0 for _ in range(n)]
a=[[] for j in range(n)]
#a 上げりゅううううううううううう
#X以上にしゅりゅうううううううううううううう
#m個全部
maxcnt = 10**9+7
for i in range(n):
	k = list(map(int,input().split()))
	c[i] = k[0]
	a[i] = k[1:]
for i in range(2**n):
	asum = [0 for _ in range(m)]
	cnt = 0
	for j in range(n):
		if ((i>>j) & 1):
			cnt += c[j]
			for k in range(m):
				asum[k] += a[j][k]
	cntj = 0
	for k in range(m):
		if asum[k] >= x:
			cntj += 1
	if cntj == m:
		if cnt <= maxcnt:
			maxcnt = cnt

if maxcnt != 10**9+7:
	print(maxcnt)
else:
	print("-1")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections

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

ok_flg = False
# 全探索
for i in range(2 ** n):
    money = 0
    skills = np.zeros(m)

    for j in range(n):
        if ((i >> j) & 1):
            money += c[j]
            skills = skills + A[j]
    if (np.all(skills >= x) and ok_flg):
        ans = min(ans, money)
    if(np.all(skills >= x) and (not ok_flg)):
        ok_flg = True
        ans = money

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

Submission status: Accepted

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

ans = 10**10
for bit in range(1<<n):
    s = [0]*m
    now = 0
    for i in range(n):
        if bit & 1<<i:
            for j in range(m):
                s[j] += C[i][j+1]
            now += C[i][0]
    if all(y >= x for y in s):
        #print(s)
        ans = min(ans,now)
if ans == 10**10:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
b = 2 ** N
minima = int(1e18)
flg = False
for i in range(b):
  S = 0
  L = [0 for _ in range(N)]
  SS = [0 for _ in range(M)]
  tmp = i
  for j in range(N):
    if tmp % 2 == 1:
      L[j] = 1
    tmp //= 2
  for k in range(N):
    if L[k] == 1:
      S += A[k][0]
      for l in range(M):
        SS[l] += A[k][l+1]
  if min(SS) >= X:
    flg = True
    if minima > S:
      minima = S
if flg:
  print(minima)
else:
  print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [[int(i) for i in input().split()] for _ in range(n)]
y = []
for b in [[i >> j & 1 for j in range(n)] for i in range(2**n)]:
    xi = [0] * m
    yi = 0
    for j, bj in enumerate(b):
        if bj == 0:
            continue
        yi += ca[j][0]
        for k in range(m):
            xi[k] += ca[j][k + 1]
    if min(xi) >= x:
        y.append(yi)
if y:
    print(min(y))
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import *
n,m,x=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(n)]
a=10**7
for i in range(1,n+1):
    for j in combinations(L,i):
        b=[0]*(m+1)
        for k in j:
            b=[b[i]+k[i] for i in range(m+1)]
        if all(i>=x for i in b[1:]):
            a=min(a,b[0])
print(-1 if a==10**7 else a)

Submission status: Accepted

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

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

ans = 10**7

for i in range(2**N):
  bit = format(i, "0" + str(N) +'b')
  skill = [0]*M
  cost = 0
  for j in range(N):
    if bit[j] == "1":
      cost += C[j][0]
      for s in range(M):
        skill[s] += C[j][s+1]

  tmp = 0
  for j in range(M):
    if skill[j] >= X:
      tmp += 1
    else:
      break
  
  if tmp == M:
    ans = min(ans,cost)
  
  #print(ans,cost,skill,bit)




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

else:
  print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n, m, x = map(int, input().split())
cas = [tuple(map(int, input().split())) for _ in range(n)]
ans = 10 ** 20

for elem in product(range(2), repeat=n):
    buy_rep = [0] * (m + 1)
    for i in range(n):
        if elem[i]:
            for j in range(1, m + 1):
                buy_rep[j] += cas[i][j]
            buy_rep[0] += cas[i][0]
    if m == len(list(filter(lambda y: x <= y, buy_rep[1:]))):
        ans = min(ans, buy_rep[0])
if ans == 10 ** 20:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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

INF = float('inf')
ans = INF

for i in range(1,2**N):
  skill = [0 for i in range(M)]
  b = 0
  for j in range(N):
    if(i>>j)&1==1:
      b += L[j][0]
      for t in range(M):
        skill[t] += L[j][t+1]
  if all([skill[y] >= X for y in range(M)]):
    #print(skill)
    ans = min(ans,b)

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

Submission status: Accepted

Solution code:
def c_skill_up():
    N, M, X = [int(i) for i in input().split()]
    Algo = [[int(i) for i in input().split()] for j in range(N)]
    ans = float('inf')
    for bits in range(1, 1 << N):
        select = []
        for d in range(N):
            if (bits >> d) & 1 == 1:
                select.append(d)

        understanding = [0] * M
        tmp = 0
        for i in select:
            c, *a = Algo[i]
            tmp += c
            for k, p in enumerate(a):
                understanding[k] += p
        if len([1 for u in understanding if u >= X]) == M:
            ans = min(ans, tmp)
    return ans if ans != float('inf') else -1

print(c_skill_up())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,x = LI()
    s = LIR(n)
    ans = float("inf")
    for b in range(1<<n):
        cost = 0
        k = [0]*m
        for i in range(n):
            if b&(1<<i):
                cost += s[i][0]
                for j in range(m):
                    k[j] += s[i][j+1]
        if cost < ans and all([i >= x for i in k]):
            ans = cost
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
p = []
c = []
for i in range(N):
    new = [int(j) for j in input().split()]
    p.append(new[0])
    c.append(new[1:])
    
flag = 0
total = [0]*M
for i in range(N):
    for j in range(M):
        total[j] += c[i][j]

for j in range(M):
    if total[j] < X:
        flag = 1
        
if flag == 1:
    print(-1)
else:
    minimum = sum(p)
    for k in range(2**N):
        total = [0]*M
        total_p = 0
        for i in range(N):
            if ((k >> i) & 1):
                total_p += p[i]           
                for j in range(M):
                    total[j] += c[i][j]
            flag2 = 0
            for j in range(M):
                if total[j] < X:
                    flag2 = 1
            if flag2==0:
                if total_p < minimum:
                    #print(total, total_p)
                    minimum=total_p
    print(minimum)