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())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = float('inf')
for i in range(2 ** N):
    tmp = [0]*M
    tmp_ans = 0
    for k in range(N):
        if 1 & i>>k:
            for l in range(1,M+1):
                tmp[l-1] += arr[k][l]
            tmp_ans += arr[k][0]
    flg = True
    for k in tmp:
        if k < X:
            flg = False
            break
    if flg:
        ans = min(ans,tmp_ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
book=[]
ans=float("inf")
for _ in range(n):
    b=list(map(int,input().split()))
    book.append(b)

for bit in range(1,2**n+1):
    al=[0 for _ in range(m+1)]
    for i in range(n):
        ch=bit%2
        bit//=2
        if ch==1:
            for k in range(m+1):
                al[k]+=book[i][k]
    if min(al[1:])>=x:
        ans=min(ans,al[0])

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

Submission status: Accepted

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

books = []

for _ in range(n):
    cost, *power = map(int, input().split())
    books.append((cost, power))


def check(levels, limit):
    for level in levels:
        if level >= limit:
            continue
        else:
            return False

    return True


candidates = []
for pattern in range(2 ** n):
    levels = [0] * m
    result = 0
    for num in range(n):
        if (pattern >> num) & 1:
            cost, powers = books[num]
            result += cost
            for idx in range(m):
                levels[idx] += powers[idx]

    if check(levels, x):
        candidates.append(result)

if not candidates:
    print(-1)
else:
    print(min(candidates))

Submission status: Accepted

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

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

import itertools

D = list(itertools.product([0, 1], repeat=n))
E = [0] * m
total = 0
ans = 0
F = []
for i in D:
    ans = 0
    E = [0] * m
    total = 0
    for j in range(len(i)):
        if i[j] == 1:
            for k in range(len(B[j])):
                E[k] += B[j][k]
            total += A[j]
    for l in E:
        if l >= x:
            continue
        else:
            ans = 1
            break
    if ans == 0:
        F.append(total)
if F == []:
    print(-1)
else:
    print(min(F))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


import itertools

n,m,x = map(int, input().split())
c = []
a = []
for i in range(n):
    cc, *aa = map(int, input().split())
    a.append(aa)
    c.append(cc)

best = None
for use in itertools.product(*[[True, False] for _ in range(n)]):
    vals = [0] * m
    nedan = sum([v for i,v in enumerate(c) if use[i]])
    for i,u in enumerate(use):
        if u:
            for j,v in enumerate(a[i]):
                vals[j] += v
    if all([item>=x for item in vals]):
        best = min(best, nedan) if best is not None else nedan
if best is not None:
    print(best)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = [int(x) for x in input().split()]
costs = []
A = []
for i in range(N):
    line = [int(x) for x in input().split()]
    costs.append(line[0])
    A.append(line[1:])

best = float('inf')
for mask in range(2 ** N):
    totalCost = 0
    skills = [0] * M
    for i in range(N):
        if (1 << i) & mask:
            totalCost += costs[i]
            for j in range(M):
                skills[j] += A[i][j]
    if all(x >= X for x in skills):
        best = min(best, totalCost)

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

Submission status: Accepted

Solution code:
import itertools
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for _ in range(N)]
ll=list(itertools.product(range(2),repeat=N))
ans=10**10
for l in ll:
    t=0
    a=[0]*M
    for i in range(N):
        if l[i]==1:
            t+=CA[i][0]
            for j in range(M):
                a[j]+=CA[i][j+1]
    for i in range(M):
        if a[i]<X:
            break
    else:
        ans=min(ans,t)
if ans==10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X= map(int,input().split())
C = []
A = []
for i in range(N):
    I = list(map(int,input().split()))
    C.append(I[0])
    A.append(I[1:])
min = 10 ** 9
for i in range(2**N):
    U = [0 for i in range(M)]
    c = 0
    I = bin(i)[2:]
    I = "0"*(N-len(I)) + I
    for j in range(N):
        if int(I[j]):
            c += C[j]
            a = A[j]
            for s in range(M):
                U[s] = U[s] + a[s]
    state = 1
    for s in range(M):
        if U[s] < X:
            state = 0
            break
    if state:
        if min >= c:
            min = c
if min ==10 ** 9:
    print(-1)
else:
    print(min)

Submission status: Accepted

Solution code:
import numpy as np

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

Cs = []
As = []
for _ in range(N):
    t = tuple(map(int, input().split()))
    Cs.append(t[0])
    As.append( np.array(t[1:]) )

mincost = 10 ** 10
for i in range(2 ** N):
    cost = 0
    skills = np.zeros(M, np.int64)
    for j in range(N):
        if i & (1 << j):
            skills += As[j]
            cost += Cs[j]
    if np.amin(skills) >= X:
        mincost = min(mincost, cost)

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

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import deque

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

c = []
a = []
for _ in range(n):
	tmp = deque(map(int,input().split()))
	c.append(tmp.popleft())
	a.append(list(tmp))

l = []
ans = 10 ** 9
for i in range(2**n):
	l = []
	tmp = 0
	for j in range(n):
			if i & (1<<j):
				l.append(j)
				tmp += c[j]
	res = [0 for _ in range(m)]
	for j in l:
		for k in range(m):
			res[k] += a[j][k]
	flag = True
	for j in range(m):
		if res[j] < x:
			flag = False
			break
	if flag:
		ans = min(ans,tmp)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(n)]
true_buy = float("inf")
for i in range(2**n):
  buy = []
  buy_sum = 0
  for j in range(n):
    if (i>>j) & 1:
      buy.append(ca[j])
      buy_sum += ca[j][0]
  for k in range(m):
    gain = 0
    for l in range(len(buy)):
      gain += buy[l][k+1]
    if gain < x:
      buy_sum = float("inf")
  true_buy = min(buy_sum,true_buy)
if true_buy == float("inf"):
  print(-1)
else:
  print(true_buy)

Submission status: Accepted

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

Submission status: Accepted

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

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

ans = float('inf')


for i in range(2 ** n):
    d = [0]*m
    tmp = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            ca = cas[j]
            c= ca[0]
            for k,a in enumerate(ca[1:]):
                d[k]+=a
            tmp+=c

    if min(d)>=x:
        ans = min(ans,tmp)

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

Submission status: Accepted

Solution code:
def main():
    N, M, X = list(map(int, input().split()))
    C = []
    A = []
    for _ in range(N):
        c, *a = list(map(int, input().split()))
        C.append(c)
        A.append(a)
    INF = 10 ** 9
    r = INF
    for pat in range(2 ** N):
        m = [sum(A[i][j] for i in range(N) if pat & (1 << i)) for j in range(M)]
        if not all(i >= X for i in m):
            continue
        c = sum(C[i] for i in range(N) if pat & (1 << i))
        r = min(r, c)
    return -1 if r == INF else r

print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


#a=[int(x) for x in input().split()]
#n=int(input())

def main():
    n,m,xk=[int(x) for x in input().split()]
    books=[ [int(x) for x in input().split()] for _ in range(n)]
    ans=10**8

    for msk in range(2**n):
        cst=0
        bk=[0]*m
        for i in range(n):
            if not msk&1<<i:
                continue
            cst+=books[i][0]
            for i,x in enumerate(books[i][1:]):
                bk[i]+=x
        # print(msk,bk)
        for k in bk:
            if k<xk:
                break
        else:
            # print("True",msk,bk,xk)
            ans=min(ans,cst)

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

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
s=[list(map(int,input().split())) for i in range(N)]
a=10**12
from itertools import product
for i in product([0,1], repeat=N):
    c=0
    for j in range(N):
        if i[j]:
            c+=s[j][0]
    if c>a:
        continue
    for j in range(M):
        t=0
        for k in range(N):
            if i[k]:
                t+=s[k][j+1]
        if t<X:
            break
    else:
        if c<a:
            a=c
print(a if a!=10**12 else -1)

Submission status: Accepted

Solution code:
#coding: utf-8
N, M, X = map(int, input().split())
L = []
ans = float("inf")
flag = False
for i in range(N):
    L.append(list(map(int, input().split())))
    # print(A)
for i in range(2**N):
    bit = i
    use = []
    skill = [0 for _ in range(M)]
    money = 0
    for j in range(N):
        if (bit >> j & 1) == 1:
            money += L[j][0]
            for k in range(1, M+1):
                skill[k-1] += L[j][k]
    tmp = True
    for k in range(M):
        if skill[k] < X:
            tmp = False
    if tmp:
        flag = True
        ans = min(ans, money)
if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
books = []
for _ in range(N):
    books.append(list(map(int,input().split())))
ans = float('inf')
for i in range(2 ** N):
    money = 0
    algo = [0 for _ in range(M)]
    for j in range(N):
        if i & 1 == 1:
            money += books[j][0]
            for k in range(M):
                algo[k] += books[j][k+1]
        i >>= 1
    if all([j >= X for j in algo]):
        ans = min(ans, money)

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

Submission status: Accepted

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

    info = [tuple(map(int, input().split())) for _ in range(N)]
    INF = 10 ** 18
    ans = INF

    for bit in range(1<<N):
        cost = 0
        x = [0] * M
        for i in range(N):
            if (bit>>i) & 1:
                cost += info[i][0]
                for j in range(M):
                    x[j] += info[i][j+1]
        
        
        if all([True if X <= y else False for y in x]):
            ans = min(ans, cost)
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

import numpy as np

def solve():
    n, m, x = MI()
    C = [0] * n
    A = [None] * n
    for i in range(n):
        tmp = LI()
        c = tmp[0]
        a = tmp[1:]
        C[i] = c
        A[i] = a
    # print(C)
    # print(A)

    ans = INF
    for i in range(pow(2, n)):
        bag = []
        for j in range(n):
            if 1 & (i >> j):
                bag.append(j)

        a = np.array([0] * m)
        c = 0
        for b in bag:
            a += np.array(A[b])
            c += C[b]

        # print(a, all(a >= x))
        if all(a >= x):
            ans = min(ans, c)

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



if __name__ == '__main__':
    solve()

Submission status: Accepted

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

ans=float("inf")

for i in range(2 ** n):
    cost = 0
    r = [0 for _ in range(m)]
    for j in range(n):
        if (i >> j) & 1:
            cost += c[j]
            for k in range(m):
                r[k] += a[j][k]
    flag = True
    for k in r:
        if k < x:
            flag = False
    if flag:
        ans = min(ans, cost)
if ans!=float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

calist=[]
for i in range(N):
  c,*alist=list(map(int,input().split()))
  calist.append((c,alist))
#print(calist)

answer=float("inf")
for perm in itertools.product(range(2),repeat=N):
  #print(perm)
  if sum(perm)==0:
    continue
    
  perm_price=0
  achieve=[0]*M
  for i in range(N):
    if perm[i]==0:
      continue
    
    ci,alist=calist[i]
    perm_price+=ci
    for j in range(M):
      achieve[j]+=alist[j]
      
  if min(achieve)>=X:
    answer=min(answer,perm_price)
    
if answer==float("inf"):
  print(-1)
else:
  print(answer)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
lis=[tuple(map(int,input().split()))for _ in range(n)]
ans = 2**60
for i in range(2**n):
    tmp = []
    vals=[0]*m
    for j in range(n):
        if i>>j&1:
            tmp.append(lis[j])
    cost=0
    flag=0
    for t in tmp:
        cost += t[0]
        for k in range(m):
            vals[k]+=t[k+1]
    for k in range(m):
        if vals[k]<x:
            flag=1
            break
    if flag:continue
    else:
        ans = min(ans,cost)
if ans == 2**60:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, m, x = map(int, input().split())
c = [0 for i in range(n)]
a = [[] for i in range(n)]
for i in range(n):
    y = list(map(int, input().split()))
    c[i] = y[0]
    a[i] = y[1:]
# print(c)
# print(a)
ans = INF
for i in range(1 << n):
    bit = bin(i)[2:].zfill(n)
    # print(bit)
    z = [0 for _ in range(m)]
    price = 0
    for j in range(n):
        if bit[j] == "1":
            price += c[j]
            for k in range(m):
                z[k] += a[j][k]
    ok = True
    for j in z:
        if j < x:
            ok = False
            break
    if ok:
        ans = min(ans, price)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

a=[[int(i) for i in input().split()] for i in range(n)]

ans=10**9
for i in range(2**n):
    status=[False]*n
    for j in range(n):
        if ((i>>j)&1):
            status[j]=True
            
    score=[0]*m
    total=0
    
    for k in range(n):
        if status[k]==True:
            for x in range(m+1):
                if x==0:
                    total+=a[k][0]
                else:
                    score[x-1]+=a[k][x]

    flag=True
    for i in score:
        if i<target:
            flag=False
    
    if flag:
        ans=min(ans,total)
if ans ==10**9:
    ans=-1
print(ans)

Submission status: Accepted

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

ans = 10 ** 7
flag = False
for i in range(1, 2 ** N):
    cost = 0
    under = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            cost += C[j]
            for k in range(M):
                under[k] += A[j][k]
    if all([val >= X for val in under]):
        ans  = min(ans, cost)
        flag = True
if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools

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

MAX = 10 ** 7
ans = MAX
for t in itertools.product((0, 1), repeat=N):
    A = [sum(t[j] * B[j][i + 1] for j in range(N)) for i in range(M)]
    if all(a >= X for a in A):
        ans = min(ans, sum(t[j] * B[j][0] for j in range(N)))
print(ans if ans != MAX else -1)

Submission status: Accepted

Solution code:
# ABC167c


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))

    n, m, x = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    rikaido = [0]*m

    def dfs(i, su):
        if i == n:
            for al in rikaido:
                if al < x:
                    return 10 ** 12
            return su
        for j in range(m):
            rikaido[j] += a[i][j+1]
        t = dfs(i + 1, su + a[i][0])
        for j in range(m):
            rikaido[j] -= a[i][j+1]
        return min(t, dfs(i+1, su))

    ans = dfs(0, 0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M, X = map(int, input().split())
c = []
A = [[] for _ in range(N)]
for j in range(N):
	tmp = list(map(int, input().split()))
	for i in range(M+1):
		if i == 0:
			c.append(tmp[i])
		else:
			A[j].append(tmp[i])
A = np.array(A)
ans = 10**10
cond = 0
for s in range(1 << N):
	flg = np.zeros(M)
	cost = 0
	for i in range(N):
		if (s >> i) & 1 == 1:
			flg += A[i]
			cost += c[i]
	if np.count_nonzero(flg < X) == 0:
		cond = 1
		ans = min(ans, cost)
if cond:
	print(ans)
else:
	print(-1)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import combinations

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    min_price = INF
    for r in range(1, N + 1):
        for comb in combinations(range(N), r):
            skills = [0] * M
            for i in range(N):
                if i in comb:
                    for j in range(M):
                        skills[j] += A[i][j]

            if all(s >= X for s in skills):
                total_price = sum(c for i, c in enumerate(C) if i in comb)
                if min_price > total_price:
                    min_price = total_price

    if min_price < INF:
        print(min_price)
    else:
        print(-1)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import pprint
import fractions
import collections
import itertools
N,M,X=map(int,input().split())
books=[list(map(int,input().split())) for _ in range(N)]
mincost=float("inf")
cando=0
for i in range(pow(2,N)):
    bit=[0]*N
    cost=0
    skill=[0]*M
    flag=1
    for j in range(N):
        if (i>>j)&1:
            bit[j]=1
    #print(bit)
    for j in range(N):
        if bit[j]==1:
            cost=cost+books[j][0]
            for k in range(1,M+1):
                skill[k-1]=skill[k-1]+books[j][k]
    for j in range(M):
        if skill[j]<X:
            flag=0
    if flag==1:
        mincost=min(mincost,cost)
        cando=1
if cando==1:
    print(mincost)
else:
    print("-1")

Submission status: Accepted

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

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

m = sum(C)+1
for i in range(2**N):
    U = [0]*M
    book = [0]*N
    for j in range(N):
        if i&(2**j) == 2**j:
            book[j] = 1
            for k in range(M):
                U[k] += A[j][k]
    det = 0
    for k in range(M):
        if U[k] < X:
            det = -1
            break

    if det == 0:
        price = 0
        for j in range(N):
            price += C[j]*book[j]
        m = min(m,price)

if m == sum(C)+1:
    print(-1)
else:
    print(m)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)

stdin = sys.stdin

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

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

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
book = list(list(map(int,input().split())) for _ in range(N))
ans = float('inf')

for i in range(2**N):
    cost = 0
    skill = [0]*M
    for j in range(N):
        if 1<<(j) & i:
            cost += book[j][0]
            for k in range(M):
                skill[k] += book[j][k+1]
    if min(skill) >= X:
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,m,x = iim()
l = []
A = list(range(n))

for _ in A:
    l.append(iil())

ans = 1e9
for i in range(1 << n):
    output = []
    for j in range(n):
        if ((i >> j) & 1) == 1:
            output.append(A[j])
    sc = [0]*(m+1)
    for k in output:
        sc = [x+y for x,y in zip(sc,l[k])]
    if min(sc[1:]) >= x:
        ans = min(ans,sc[0])
print(ans if ans < 1e9 else -1)

Submission status: Accepted

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

MY_INF = 1000000007
    
ans = MY_INF
for case in range(1 << N):
    ans_tmp = 0
    A_tmp = [0] * M
    case_tmp = case
    for i in range(N):
        if case_tmp % 2:
            ans_tmp += C[i]
            for j, Aij in enumerate(A[i]):
                A_tmp[j] += Aij
        #
        case_tmp >>= 1
    #
    for j in range(M):
        if A_tmp[j] < X:
            break
        else:
            continue
    else:
        ans = min(ans, ans_tmp)
else:
    if ans == MY_INF: ans = -1

print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

ans=float('inf')
for i in range(2**n):
    lst=[0]*m
    tmp=0
    for j in range(n):
        if i>>j&1:
            tmp+=ca[j][0]
            for k in range(m):
                lst[k]+=ca[j][k+1]

    # print(lst)
    # print(i,tmp)

    for j in range(m):
        if lst[j]>=x:
            pass
        else:
            break
    else:
        ans=min(ans,tmp)

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