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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


N,M,K = m()
po = []
for i in range(N):
    po.append(l())

ans = Max

for i in range(2**N):
    kane = 0
    un = [0 for _ in range(M)]
    no = i
    for j in range(N):
        ppp = no % 2
        if ppp:
            for k in range(M+1):
                if k == 0:
                    kane += po[j][k]
                else:
                    un[k-1] += po[j][k]
        no //=2
    if all(map(lambda x:x >= K,un)):
        ans = min(ans,kane)
if ans != Max:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:

N, M, X = map(int, input().split())
prices = []
effects = []
for _ in range(N):
	values = list(map(int, input().split()))
	prices.append(values[0])
	effects.append(values[1:])

sum_price = sum(prices)
min_price = sum_price + 1

for n in range(2 ** N):
	price = 0
	understood = [0] * M
	i = 0
	while n > 0:
		if n % 2 == 1:
			price += prices[i]
			for j in range(M):
				understood[j] += effects[i][j]
		i += 1
		n //= 2
	if all(understood[j] >= X for j in range(M)):
		if price < min_price:
			min_price = price

if min_price > sum_price:
	print(-1)
else:
	print(min_price)

Submission status: Accepted

Solution code:
import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M, X = map(int,readline().split())
ca = np.array([list(map(int, readline().split())) for _ in range(N)])
#ca = np.array(sorted(ca, key=lambda x: -sum(x[1:])))

#ca = np.array(sorted(ca, key=lambda x: x[0]))

ans = pow(10, 9) + 7
#count = np.zeros(M)
flag = False
for bit in range(0, 1<<N):
    acc = 0
    count = np.zeros(M)
    for i in range(N):
        if bit & (1<<i):
            ca_ = ca[i]
            acc += ca_[0]
            count += ca_[1:]
    if count.min() >= X:
        ans = min(ans, acc)
        flag = True
    
print(ans) if flag else print(-1)

Submission status: Accepted

Solution code:
def bit_all(x):
    price = 0
    ret = [0] * M
    b = str(format(x, "012b"))
    for i in range(N):
        if b[- (i + 1)] == "1": 
            for j in range(M):
                ret[j] += A[i][j]
            price += C[i]
            
    return price, ret

N, M, X = list(map(int,input().split()))
C = []
A = []
for i in range(N):
    input_ = list(map(int,input().split()))
    C.append(input_[0])
    A.append(input_[1 : M + 1])
    
ans = 10 ** 9 + 7
for x in range(2 ** N):
    price, ret = bit_all(x)
    if min(ret) >= X:
        ans = min(price, ans)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m,x = map(int,input().split())
clist = []
alist = []
ans = 10**20
for i in range(n):
    ca = list(map(int,input().split()))
    c = ca[0]
    a = ca[1:]
    clist.append(c)
    alist.append(a)

for i in range(2**n):
    y = 0
    rikai = [0]*m
    bi = bin(i)[2:].zfill(n)
    for j in range(n):
        if bi[j] == '1':
            y += clist[j]
            for k in range(m):
                rikai[k] += alist[j][k]
    for j in range(m):
        if rikai[j] < x:
            break
    else:
        ans = min(ans,y)
if ans == 10**20:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
def hani(x,min_,max_):
    ret=x
    if x<min_:ret=min_
    if x>max_:ret=max_
    return ret
def seifu(x):
    return x//abs(x)
###################################################

def main():
    N,M,X=list(map(int,input().split()))
    C=[]
    A=[]
    for a in range(N):
        tmp=list(map(int,input().split()))
        C.append(tmp[0])
        A.append(tmp[1:])
    ans=inf
    for a in range(1<<N):
        B=bin_(a,N)
        rikai=[0]*M
        cost=0
        for b in range(N):
            if B[b]==1:
                cost+=C[b]*B[b]
                for c in range(M):
                    rikai[c]+=A[b][c]
        if min(rikai)>=X:
            ans=min(ans,cost)
    if ans==inf:
        print(-1)
    else:
        print(ans)


main()

Submission status: Accepted

Solution code:

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

ans = 10**1000
for i in range(2**N):
    prc = 0
    li = [0 for _ in range(M)]
    for j in range(N):
        if (i>>j)&1:
            prc += A[j][0]
            for k in range(M):
                li[k] += A[j][k+1]
    # print(bin(i),prc,li)
    for k in range(M):
        if li[k]<X:
            break
    else:
        ans = min(prc,ans)
if ans == 10**1000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
INF=float("inf")
n, m, x = map(int, input().strip().split())
L = [list(map(int, input().split())) for _ in range(n)]

ans=INF
for i in range(2**n):
    bin_=i
    money=0
    rikaido=[0]*m
    book=0
    while bin_:
        if bin_ & 1: # read
            money+=L[book][0]
            for j in range(m):
                rikaido[j]+=L[book][j+1]
        bin_>>=1
        book+=1
    for j in range(m):
        if rikaido[j]<x:
            break
    else:
        ans=min(ans,money)
        
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,X = map(int,input().split())
A = []
for i in range(N):
    a = list(map(int,input().split()))
    A.append(a)
ans = 10 ** 10
Z = [0,1]
Y = list(itertools.product(Z,repeat=N))
for y in Y:
    tmp = [0 for i in range(M)]
    ctmp = 0
    for i in range(N):
        if y[i] == 1:
            ctmp += A[i][0]
            for j in range(M):
                tmp[j] += A[i][j+1]
    check = 0
    for k in tmp:
        if k < X:
            check = 1
    if check == 0:
        if ctmp < ans:
            ans = ctmp
if ans == 10 ** 10:
    ans = -1
print(ans)

Submission status: Accepted

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

def main():
    N, M, X = map(int, input().split())
    C = [None] * N
    A = [None for _ in range(N)]
    for i in range(N):
        C[i], *A[i] = map(int, input().split())
    
    # print(C,A)
    ans = 10**12
    for i in range(2**N):
        tmp = [0] * M
        tmpC = 0
        for j in range(N):
            if (i >> j) & 1:
                for k in range(M):
                    tmp[k] += A[j][k]
                tmpC += C[j]
        flag = True
        for k in range(M):
            if tmp[k] < X:
                flag = False
                break
        if flag:
            ans = min(ans, tmpC)
    
    if ans == 10**12:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

res = 10 ** 9
for i in range(2 ** N):
    c = 0
    s = [0 for _ in range(M)]
    for j in range(N):
        if i & (2 ** j):
            c += C[j]
            for k in range(M):
                s[k] += L[j][k]
    f = 1
    for j in range(M):
        if s[j] < X:
            f = 0
            break
    if f:
        res = min(res, c)

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

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np


def submit():
    n, m, x = map(int, input().split())
    books = {}
    for i in range(n):
        e = list(map(int, input().split()))
        c = e[0]
        books[i] = (c, np.array(e[1:]))

    min_cost = float("inf")
    for pt in product([0, 1], repeat=n):
        curr_cost = 0
        curr_skills = np.zeros(m)
        for i, isbuy in enumerate(pt):
            if isbuy: # book iを買ったことにする
                cost, skills = books[i]
                curr_cost += cost
                curr_skills += skills

            if np.all(curr_skills >= x) and curr_cost < min_cost:
                min_cost = curr_cost

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


submit()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N,M,X = map(int, input().split())
    ca = []
    res = sys.maxsize
    for _ in range(N):
        ca.append(list(map(int, input().split())))
    for i in range(2 ** N):
        tmp = [0]*M
        tmpres = 0
        for j in range(N):
            if ((i >> j) & 1):
                tca = ca[N-1-j]
                tmpres += tca[0]
                for k in range(M):
                    tmp[k] += tca[1+k]
        tassei = True
        for a in tmp:
            if a < X:
                tassei = False
                break
        if tassei:
            res = min(res,tmpres)
    if res != sys.maxsize:
        print(res)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M, X = map(int, input().split())

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

for i in range(M):
    x = sum([a[i] for a in A])
    if x < X:
        print(-1)
        exit()


ans = float('inf')
def solve(buf):
    global ans

    if len(buf) == N:
        can_solve = True
        for i in range(M):
            x = sum([A[j][i] for j in range(N) if buf[j]])
            if x < X:
                can_solve = False
                break

        if can_solve:
            c =  sum([C[j] for j in range(N) if buf[j]])
            ans = min(ans, c)

    else:
        solve(buf + [0])
        solve(buf + [1])

#
solve([])
print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())  # N冊の参考書, M個のアルゴリズム, X以上にしたい
books = [list(map(int, input().split())) for _ in range(N)]
ans = float("inf")
for mask in range(1 << N):  # 2のd乗になる
    binary = []
    for i in range(N):
        binary.append((mask >> i) & 1)
    # bitが立っている参考書だけを購入する
    tmp_cost = 0
    now_understand = [0]*M
    for i in range(N):
        if binary[i] == 1:
            c, *A = books[i]
            tmp_cost += c
            for j in range(len(A)):
                now_understand[j] += A[j]

    flag = True
    for i in range(M):
        if now_understand[i] < X:
            flag = False

    if flag:
        ans = min(ans, tmp_cost)

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

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(n)]
P = list(itertools.product([0,1], repeat=n))

MIN=10000000000
for p in P:
    ans = 0
    now = [0]*m
    for i in range(n):
        if p[i]==1:
            ans += ca[i][0]
            for g in range(1,m+1):
                now[g-1] += ca[i][g]
    frag = True
    for i in range(m):
        if now[i]<x:
            frag = False
            break
    if frag:
        MIN = min(ans,MIN)

if MIN == 10000000000:
    print(-1)
else:
    print(MIN)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
c = []
for i in range(n):
  a = [int(i) for i in input().split()]
  c.append(a)
  
c = np.array(c)
ans = float('inf')
for i in range(1,2**n):
  chk = [0]*m
  cost = 0
  for j in range(n):
    if (i>>j)&1 == 1:
      cost += c[j][0]
      chk += c[j][1:]
  if min(chk) >= x:
    ans = min(ans,cost)
  
if ans == float('inf'):
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N,M,X = map(int, input().split())
arr = np.array([list(map(int, input().split())) for _ in range(N)])
und=[0]*M
c_max = 10**7

for i in range(N):
    lis=list(itertools.combinations(arr,i+1))
    for li in lis:
        c=0
        a=np.array([0]*M)
        for l in li:
            c += l[0]
            a += l[1:]
        #print(li,c,a)
        if np.all(a>=X) and c<c_max:
            c_max=c
if c_max < 10**7:
    print(c_max)
else:
    print('-1')

Submission status: Accepted

Solution code:
import numpy as np

n,m,x = map(int, input().split())
c = []
a = []
s =  np.zeros(m)
for i in range(n):
    temp = list(map(int, input().split()))
    c.append(temp[0])
    a.append(temp[1:])
    s+=np.array(temp[1:])

a = np.array(a)

if (min(s) < x):
    print(-1)
else:
    ans = np.inf
    for i in range(0, 2 ** n):
        ct = bin(i)[2:].zfill(n)
        price = 0
        score = np.zeros(m)
        for j in range(n):
            score += int(ct[j]) * a[j]
            price += int(ct[j]) * c[j]
        if (min(score) >= x):
            ans = min(price,ans)
    print(ans)

Submission status: Accepted

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

import itertools
import sys


INF = sys.maxsize // 10


def all_subsets(xs):
    n = len(xs)
    gs = (itertools.combinations(xs, i) for i in range(n + 1))
    return itertools.chain(*gs)


def optimize(n, m, x, cs, table):
    res = INF
    for book_ids in all_subsets(list(range(n))):
        unds = [0 for _ in range(m)]
        cost = 0
        for book_id in book_ids:
            cost += cs[book_id]
            for j, a in enumerate(table[book_id]):
                unds[j] += a
        if all(und >= x for und in unds):
            res = min(res, cost)
    return res


def main():
    n, m, x = (int(z) for z in input().split())
    cs = [0 for _ in range(n)]
    table = [None for _ in range(n)]
    for i in range(n):
        ys = [int(z) for z in input().split()]
        cs[i] = ys[0]
        table[i] = ys[1:][:]
    res = optimize(n, m, x, cs, table)
    if res < INF:
        print(res)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = 10**12
for i in range(1<<n):
    rikai  = [0] * m
    cost = 0
    bs = bin(i)[2:]
    bs = bs.zfill(n)
    # print(bs)
    for j,b in enumerate(bs):
        if b == "1":
            # 本を購入
            cost += C[j]
            for k in range(m):
                rikai[k] += A[j][k]            
    a = sum([1 for r in rikai if r >= x])
    if a == m:
        ans = min(ans,cost)
print(ans if ans != 10**12 else -1)

Submission status: Accepted

Solution code:
def resolve():
    import itertools
    impossible = 10 ** 20
    n, m, x = map(int, input().split())
    ans = impossible
    books = [None] * n
    for i in range(n):
        books[i] = list(map(int, input().split()))
    for i in list(itertools.product([True, False], repeat=n)):
        u = [0] * m
        yen = 0
        for index, j in enumerate(i):
            if not j:
                continue
            yen += books[index][0]
            for k in range(m):
                u[k] += books[index][k + 1]
        for j in u:
            if j < x:
                break
        else:
            ans = min(yen, ans)
    print(ans if ans < impossible else -1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import numpy as np
N, M, X = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(N)]
INF = 10**30
min_cost = INF
for pattern in range(1<<N):
    skills = np.array([0]*M)
    cost = 0
    for i in range(N):
        if pattern >> i & 1:
            skil = np.array(books[i][1:])
            skills += skil
            cost += books[i][0]
    if min(skills) >= X and cost < min_cost:
        min_cost = cost
if min_cost == INF:
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

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

ans=10**9
for i in range(2**n):
    s=format(i,'b')
    Z=s.zfill(n)
    cost=0
    M=[0]*m
    for j in range(n):
        if Z[j]=='1':
            cost+=X[j][0]
            for k in range(m):
                M[k]+=X[j][1+k]
    if all([m>=x for m in M]):
        ans=min(ans,cost)

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N, M, X = map(int, input().split())
books = list()
for _ in range(N):
    books.append(list(map(int, input().split())))
    
A = [False, True]
combinations = list(itertools.product(A, repeat=N))
books_array = np.array(books)
amount = float('inf')
check = False
for comb in combinations:
    array = books_array[np.array(comb).T]
    amo = array[:, 0].sum()
    if np.all(array[:, 1:].sum(axis=0) >= X) and amo < amount:
        amount = amo
        check = True

if check:
    print(amount)
else:
    print(-1)

Submission status: Accepted

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

ans = INF
for i in range(2**n):
    tmp = 0
    tmp_l = [0]*m
    for j in range(n):
        if i & (1<<j):
            tmp += ca[j][0]
            for k in range(m):
                tmp_l[k] += ca[j][1+k]
    if min(tmp_l) >= x:
        ans = min(ans, tmp)
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,M,X = LMIIS()
    books = []
    for _ in range(N):
        books.append(LMIIS())
    up = 12 * 10**5 + 1
    min_cost = up
    for i in range(2**N):
        algo = [0]*M
        cost = 0
        for j in range(N):
            if i & (2**j):
                cost += books[j][0]
                for k in range(M):
                    algo[k] += books[j][k+1]
        if min(algo) < X:
            continue
        min_cost = min(min_cost,cost)
    print(min_cost if min_cost != up else -1)

        



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
########10進法からn進法への変換関数部分##############
def format(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
############################
########10進法からn進法への変換関数(m桁埋める)部分##############
def format0(X, n, m):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    if len(out) < m:
        out = "0" * (m - len(out)) + out
    return out
############################
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
mo=10000000000000
import numpy
for i in range(1,pow(2,n)):
  i=format0(i,2,n)
  money=0
  aaa=[0]*m
  aaa=numpy.array(aaa)
  for j in range(n):
    if i[j]=="1":
      money+=ca[j][0]
      aaa = aaa + numpy.array(ca[j][1:])
  if aaa.min()>=x:
    mo=min(mo,money)
  else:
    if i=="1"*n:
      print("-1")
      exit()
print(mo)

Submission status: Accepted

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


def calc(isBuy):
    global min_cost
    understands = [0 for _ in range(M)]
    cost = 0
    for i in range(N):
        if isBuy[i]:
            cost += Cs[i]
            for j in range(M):
                understands[j] += As[i][j]

    isClear = True
    for und in understands:
        if und < X:
            isClear = False

    if isClear:
        min_cost = min(min_cost, cost)


def search(isBuy):
    if len(isBuy) == N:
        calc(isBuy)
    else:
        search(isBuy + [True])
        search(isBuy + [False])


min_cost = float('inf')
search([])

if min_cost < float('inf'):
    print(min_cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
N, M, X = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]
ans = 10**20
q = deque()
q.append([])
while q:
  x = q.pop()
  if len(x) == N:
    U = [0]*M
    i = 0
    while i < N:
      if x[i]:
        j = 0
        while j < M:
          U[j] += B[i][j+1]
          j += 1
      i += 1
    if len(list(filter(lambda x:x< X, U))) < 1:
      ans = min(ans, sum([B[i][0] if x[i] else 0 for i in range(N)]))
  else:
    q.append(x+[True])
    q.append(x+[False])
print(ans if ans < 10**20 else -1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N, M, X = map(int, input().split())

C = []
A = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    c = tmp[0]
    a = tmp[1:]
    C.append(c)
    A.append(a)
A = np.array(A)

ans = 10**18
for bit in range(1 << N):
    cost = 0
    V = np.array([0] * M)
    for i in range(N):
        if bit & 1 << i:
            cost += C[i]
            V += A[i]
    if np.all(V >= X):
        ans = min(ans, cost)
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
CA = [list(map(int,input().split())) for _ in range(N)]
judge = False
ans = float('inf')
for i in range(2**N):
  lis = []
  for j in range(N):
    if (i>>j)&1:
      lis.append(CA[j])
  
  rikaido = [0]*M
  tmp_ans = 0
  tmp_judge = True
  for j in lis:
    tmp_ans += j[0]
    for k,x in enumerate(j[1:]):
      rikaido[k] += x
  
  for j in rikaido:
    if j>=X:
      continue
    else:
      tmp_judge = False
      break
  
  if tmp_judge:
    judge = True
    ans = min(ans,tmp_ans)
    
if judge:
  print(ans)
else:
  print(-1)

Submission status: Accepted

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

ans=10**10
for i in range(2**n):
    num=format(i,"b").zfill(n)
    C=[0 for _ in range(m)]
    point=0
    for j,k in enumerate(num):
        if k=="1":
            c,B=A[j][0],A[j][1:]
            for v,s in enumerate(B):
                C[v] +=s
            point +=c
    flag=1
    for i in range(m):
        if C[i]>=x:continue
        else:
            flag=0
            break
    if flag:ans=min(ans,point)
print(ans if ans!=10**10 else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys

sys.setrecursionlimit(210000)
MAX_VAL = 1000000000


def search(idx, books, reqs):
  if max(reqs) <= 0:
    return 0

  if idx >= len(books):
    return MAX_VAL

  cost0 = search(idx + 1, books, reqs)

  reqs = [r - s for r, s in zip(reqs, books[idx][1:])]
  cost1 = search(idx + 1, books, reqs) + books[idx][0]

  return min(cost0, cost1)


def main():
  N, M, X = map(int, input().split())
  books = [list(map(int, input().split())) for _ in range(N)]
  reqs = [X] * M
  cost = search(0, books, reqs)

  if cost < MAX_VAL:
    print(cost)
  else:
    print(-1)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict

N, M, X = map(int, input().split())
B = []
for i in range(N):
    B.append(list(map(int, input().split())))
ans = 10**18
for i in range(1<<N):
    c = 0
    r = [0]*M
    for j in range(N):
        if (i>>j)&1:
            c += B[j][0]
            for k in range(1, M+1):
                r[k-1] += B[j][k]
    if all([x >= X for x in r]):
        ans = min(ans, c)
if ans == 10**18:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a_list = []
c_list = []
for i in range(n):
    a = [int(i) for i in input().split()]
    a_list.append(a[1:])
    c_list.append(a[0])
ans = -1
for j in range(2 ** n):
    ans_list = [0] * m
    cost = 0
    for i in range(n):
        if j & (2 ** i) > 0:
            for index, k in enumerate(a_list[i]):
                ans_list[index] += k
            cost += c_list[i]
    if sum([1 for i in ans_list if i >= x]) == m:
        if ans == -1:
            ans = cost
        else:
            ans = min(ans, cost)
print(ans)

Submission status: Accepted

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

ans = 10**10
for i in range(2 ** n):
    state = [0] * n
    for j in range(n):
        state[j] = (i >> j) & 1
    #print(state)
    num = [0] * m
    val = 0

    for j in range(n):
        if state[j] == 1:
            for k in range(m):
                num[k] += c[j][k+1]
            val += c[j][0]

    flag = True
    for j in range(m):
        if num[j] < x:
            flag = False
            break
    if flag:
        ans = min(ans, val)

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