Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import combinations
N, M, X = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for i in range(N):
    tmp = [int(x) for x in stdin.readline().rstrip().split()]
    data.append(tmp)

ans = 10**18
for i in range(1, N+1):
    for j in combinations(data, i):
        C = 0
        rikai = [0]*M
        for l in j:
            C += l[0]
            for ind, k in enumerate(l[1:]):
                rikai[ind] += k
        if len([i for i in rikai[:] if i >= X]) == M:
            ans = min(C, ans)
if ans == 10**18:
    ans = -1
print(ans)

Submission status: Accepted

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

#print(a[0][1]):
pattern=[]
for i in range(2**n):
    tmp = [False]*n
    for j in range(n):
        if i >> j & 1:
            tmp[j] = True
    pattern.append(tmp)

#print(pattern)
kaisu=len(pattern)
ans=10**9
for i in range(kaisu):
    List=[0]*(m+1)
    for j in range(n):
        if (pattern[i][j]==True):
            for l in range(m+1):
                List[l]+=a[j][l]
    flag=0
   # print(List)
    for k in range(1,m+1):
        if (List[k]<x):
            flag=1
            break
    if (flag==0):
        ans=min(ans,List[0])

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

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


n,m,x = mi()
C = [[] for _ in range(n)]

for i in range(n):
    c = li()
    for l in range(m+1):
        C[i].append(c[l])


anss = 10**9
for i in range(1<<n):
    alis = [0]*m
    ans = 0
    for k in range(n):
        if i>>k & 1:
            ans += C[k][0]
            for l in range(m):
                alis[l] += C[k][l+1]
    flag = 1
    for l in range(m):
        if alis[l] < x:
            flag = 0
    if flag:
        anss = min(anss,ans)

if anss == 10**9:
    print(-1)
    exit()
print(anss)

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m,y=MI()
lis=[LI() for i in range(n)]
u=[]
point=[0 for i in range(m)]
for i in range(2**n):
    pay=0
    point=[0 for i in range(m)]
    for j in range(n):
        x=(i>>j) %2
        if x==1:
            for k in range(1,m+1):
                point[k-1]+=lis[j][k]
            pay+=lis[j][0]
    #print(min(point))
    if min(point)>=y:
        u.append(pay)
    #print(y)
if len(u)>0:
    print(min(u))
else:
    print("-1")

Submission status: Accepted

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

buys = []
for i in range(2**N):
    buy = []
    for j in range(N):
        if ((i>>j) & 1):
            buy.append(j)
    buys.append(buy)

ans = 10**9
flag = 1
for books in buys:
    cost = 0
    power = [0] * M
    for book in books:
        cost += C[book]
        for i in range(M):
            power[i] += A[book][i]

    if min(power) >= X:
        ans = min(ans, cost)
        flag = 0

print(-1 if flag else ans)

Submission status: Accepted

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


input = sys.stdin.readline
def IS(cb): return cb(input().strip())
def IL(cb): return [cb(s) for s in input().strip().split()]
def IR(cb, rows): return [IS(cb) for _ in range(rows)]
def ILL(cb, rows): return [IL(cb) for _ in range(rows)]


def solve():
    N, M, X = IL(int)
    CA = ILL(int, N)
    ans = float('Inf')
    ok = False
    for bit in range(2 ** N):
        skill = [0] * M
        cost = 0
        for i in (b for b in range(N) if (0x01 << b) & bit):
            for j in range(M):
                skill[j] += CA[i][j + 1]
            cost += CA[i][0]
        if all(j >= X for j in skill):
            ok = True
            ans = min(ans, cost)

    print(ans if ok else -1)


solve()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c=[0 for _ in range(n)]
a=[[] for _ in range(n)]
for i in range(n):
    c[i],*a[i] = map(int,input().split())
ans=sum(c)+1
alg=[0 for i in range(m)]
for i in range(int(2**n)):
    cnt=0
    al=alg[:]
    ii=i
    for j in range(n):
        r=i%2
        i=i//2
        if r ==1:
            cnt+=c[j]
            k=0
            for v in a[j]:
                al[k]+=v
                k+=1
    ok = True
    for y in al:
        if y<x:
            ok=False
            break
    if ok:
        ans=min(ans,cnt)
    #print(ii,cnt,al)
if ans==sum(c)+1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

A=[]
C=[]


for i in range(int(N)):
    S=input().split()
    C.append(int(S[0]))
    A.append([int(a) for a in S[1:]])

L=2**int(N)
ans=[]
for i in range(L):
    D=[0]*int(M)
    Z='{:012b}'.format(i)
    c=0
    for j in range(int(N)):
        if int(Z[11-j])==1:
            c+=C[j]
            for m in range(int(M)):
                D[m]+=A[j][m]           
    if min(D)>=int(X):
        ans.append(c)

#print(ans)
if ans==[]:
    ans=-1
else:
    ans=min(ans)

print(ans)

Submission status: Accepted

Solution code:
c,m,x=map(int,input().split())
book=[list(map(int,input().split())) for i in range(c)]
ans=[False,float('inf')]
for i in range(1<<c):
  p=[0 for i in range(m)]
  num=0
  money=0
  while i>0:
    if i&1==1:
      money+=book[num][0]
      for j in range(1,m+1):
        p[j-1]+=book[num][j]
    num+=1
    i=i>>1
  if min(p)>=x and ans[1]>money:
    ans[0]=True
    ans[1]=money
if ans[0]:
  print(ans[1])
else:
  print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
import numpy as np
books = [list(map(int, input().split())) for _ in range(N)]

ans = 10**18
for i in range(1<<N):
    algo = np.array([0]*M)
    cost = 0
    for j in range(N):
        if (i>>j)&1:
            c, *al = books[j]
            al = np.array(al)
            algo += al
            cost += c
    if np.all(algo>=X):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,x=n1()
ca=n3(n)
ca

import itertools
book=list(itertools.product([0,1], repeat=n))
price=[]
for line in book:
    p=0
    for i in range(n):
        if line[i]==1:
            p+=ca[i][0]
            
    price.append(p)
A=[[book[i],price[i]] for i in range(len(book))]
A.sort(key=lambda x:x[1])

for line in A:
    t=line[0]
    s=[0]*m
    for i in range(n):
        if t[i]==1:
            s=[s[j]+ca[i][j+1] for j in range(m)]
    if len([i for i in s if i>=x])==m:
        print(line[1])
        break
else:
    print(-1)

Submission status: Accepted

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

ans = float('inf')
for i in range(2 ** N):
    s = []
    for j in range(N):
        if (i >> j) & 1:
            s.append(j)

    # print(s)
    cost = 0
    score = [0] * M
    for t in s:
        cost += C[t]
        for k, a in enumerate(A[t]):
            score[k] += a
    # print(score)
    flag = True
    for sc in score:
        if sc < X:
            flag = False
            break
    if flag:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C = [0] * N
A = [ [0 for i in range(M)] for i in range(N) ]
for i in range(N):
  CA = list(map(int,input().split()))
  C[i] = CA[0]
  A[i] = CA[1:]
INF = 100000000
ans = INF
for i in range( 1 << N ):
  cost = 0
  r = [0] * M
  for j in range(N):
    if (i & (1 << j) != 0):
      cost += C[j]
      for k in range(M):
        r[k] += A[j][k]
  ok = 1
  for k in range(M):
    if r[k] < X:
      ok = 0
  if ok == 1:
    ans = min(ans, cost)
#  print(" ",i," ",ok)
#  print(" ",r)
if ans == INF:
  print("-1")
else:
  print(ans)

Submission status: Accepted

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

from itertools import combinations

minprice = 10**13
for i in range(1, n + 1):
    l = list(combinations(range(n), i))
    for singleper in l:
        res = [0] * m
        price = 0
        for single in singleper:
            for j in range(m):
                res[j] += a[single][j]
            price += c[single]
        ok = True
        for j in range(m):
            if res[j] < x:
                ok = False
                break
        if ok:
            minprice = min(minprice, price)

if minprice == 10**13:
    print(-1)
else:
    print(minprice)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np

N, M, X = map(int, input().split())
d = []
money = []

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

ans = 10 ** 9
for i in range(1, 2 ** N + 1):
    bought = []
    okane = 0
    for k in range(N):
        if i >> k & 1 == 1:
            bought.append(d[k])
            okane += money[k]
    total = np.zeros(M)
    for j in bought:
        total += j
    if sum(total >= X) == M:
        ans = min(ans, okane)

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

Submission status: Accepted

Solution code:
n,m,x=(int(i) for i in input().split())
l=[]
ans=None
for i in range(n):
  l.append([int(i) for i in input().split()])
for i in range(2**n):
  k=i
  r=[0 for i in range(m)]
  cost=0
  for j in range(n):
    if k%2==1:
      for y in range(m):
        r[y]+=l[j][y+1]
      cost+=l[j][0]
    k=k//2
  if min(r)>=x:
    if ans==None:
      ans=cost
    elif ans>cost:
      ans=cost
if ans==None:
  print('-1')
else:
  print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca_list = [[int(i) for i in input().split()] for _ in range(n)]
ans = 999999999999999
flag = 0

for i in range(2**n):
  bin_str = format(i, '0'+str(n)+'b')
  skill_list = [0]*m
  cost = 0
  for j, ca in enumerate(ca_list):
    if bin_str[j] == "1":
      cost += ca[0]
      for k in range(m):
        skill_list[k] += ca[k+1]
  if all([i >= x for i in skill_list]):
    ans = min(ans, cost)
    flag = 1
print(ans if flag == 1 else -1)

Submission status: Accepted

Solution code:
import sys


N, M, X = map(int, input().split())
A = [None] * N
C = [None] * N
for i, s in enumerate(sys.stdin.readlines()):
    C[i], *A[i] = map(int, s.split())

ans = 10 ** 8
for i in range(1 << N):
    k = 0
    v = 0
    S = [0] * M
    while (i >> k) > 0:
        if (i >> k) & 1:
            for j in range(M):
                S[j] += A[k][j]
            v += C[k]
        k += 1

    if all(a >= X for a in S):
        ans = min(ans, v)
        

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

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, M, X = [int(x) for x in input().strip().split()]
    C = [0] * N
    A = [[0 for _ in range(M)] for _ in range(N)]
    for n in range(N):
        ca = [int(x) for x in input().strip().split()]
        C[n] = ca[0]
        A[n] = ca[1:]
    ans = float('inf')
    for i in range(1 << N):
        A_ = [0] * M
        ans_ = 0
        for j in range(N):
            if i >> j & 1 == 1:
                for m in range(M):
                    A_[m] += A[j][m]
                ans_ += C[j]
        f = True
        for m in range(M):
            if A_[m] < X:
                f = False
                break
        if f:
            ans = min(ans, ans_)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
N, M, X = [int(i) for i in input().split()]
ans = float("inf")
CA = [[int(i) for i in input().split()] for _ in range(N)]
for i in range(1, N + 1):
    for j in combinations(list(range(N)), i):
        ary = [0 for _ in range(M)]
        c = 0
        for k in j:
            c += CA[k][0]
            for i, l in enumerate(CA[k][1:]):
                ary[i] += l
        if all([x >= X for x in ary]):
            ans = min(c, ans)
print(ans if ans < float("inf") else -1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
cc=[list(map(int,input().split())) for _ in range(n)]
from itertools import combinations
s=list(range(n))
ans=10**10
array=[0]*m
res=0
for ii in range(1,n+1):
    for i in combinations(s,ii):
        for j in i:
            res+=cc[j][0]
            for k,l in enumerate(cc[j][1:]):
                array[k]+=l
        if min(array)>=x:
            ans=min(ans,res)
        res=0
        array=[0]*m
    
if ans==10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

n, m, x = [int(i) for i in input().split()]
table = [[int(i) for i in input().split()] for _ in range(n)]
costs = [i[0] for i in table]
acc = [i[1:] for i in table]

ret = 10 ** 9
for i in itertools.product([True, False], repeat=n):
  algos = np.zeros(m)
  for book, t_f in enumerate(i):
    if t_f:
      algos += acc[book]
  if np.all(algos >= x):
    ret = min(ret, (np.array(costs) * i).sum())

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

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, m, x = map(int, args[0].split())
    inf = 10**12

    C = []
    A = []
    for CA in map(str.split, args[1:]):
        C.append(int(CA[0]))
        A.append(CA[1:])

    A = np.array(A, int)

    ret = inf
    for b in range(2**n):
        S = np.zeros(m, int)
        c = 0
        for i in range(n):
            if (b >> i) & 1 == 1:
                S += A[i]
                c += C[i]
            if all(x <= S):
                ret = min(ret, c)

    return str(ret if ret < inf else -1)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import itertools
N, M, X = map(int, input().split())
C = []
A = []
ans = -1
for i in range(N):
  tmp = list(map(int, input().split()))
  C.append(tmp[0])
  A.append(tmp[1:])
for bit in itertools.product([0,1], repeat=N):
  tmpX = [0 for _ in range(M)]
  tmpC = 0
  for i in range(N):
    if bit[i] == 1:
      for j in range(M):
        tmpX[j] += A[i][j]
      tmpC += C[i]
  flag = True
  for i in range(M):
    if tmpX[i] < X:
      flag = False
      break
  if not flag:
    continue
  if ans == -1:
    ans = tmpC
  else:
    ans = min(ans, tmpC)
print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
cursor=n
current=[0]*n
mincost=1000000000000000000000
breakflag=0
while True:
  thing=[0]*m
  cost=0
  for i in range(n):
    if current[i]==1:
      cost+=a[i][0]
      for j in range(m):
        thing[j]+=a[i][j+1]
  success=1
  for j in range(m):
    if thing[j]<x:
      success=0
  if success==1 and cost<mincost:
    mincost=cost
  while True:
    if current[cursor-1]<1:
      current[cursor-1]+=1
      for i in range(cursor,n):
        current[i]=0
      cursor=n
      break
    cursor-=1
    if cursor==0:
      breakflag=1
      break    
  if breakflag==1:
    break
if mincost==1000000000000000000000:
  print(-1)
else:
  print(mincost)

Submission status: Accepted

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

ans = -1
for bits in range(2 ** N):
    cost = 0
    param = [0] * M
    for i in range(N):
        if (bits >> i) & 1 == 1:
            cost += CA[i][0]
            for j in range(M):
                param[j] += CA[i][j + 1]

    if min(param) >= X:
        ans = min(ans, cost) if ans != -1 else cost

print(ans)

Submission status: Accepted

Solution code:
import sys
l = sys.stdin.readline().strip()
N, M, X = map(int, l.split())
A = []
C = []
for i in range(N):
    l = sys.stdin.readline().strip()
    a = list(map(int, l.split()))
    C.append(a[0])
    A.append(a[1:])

price = float("INF")
for i in range(2**N):
    bits = bin(i)[2:]
    while len(bits) < N:
        bits = '0' + bits
    bits = list(bits)
    good = True
    for j in range(M):
        crt = 0
        for k, b in enumerate(bits):
            if b == '1':
                crt += A[k][j]
        if crt < X:
            good = False
            break
    if good:
        p = 0
        for k,b in enumerate(bits):
            if b == '1':
                p += C[k]
        if p < price:
            price = p

if price == float("INF"):
    print(-1)
else:
    print(price)

Submission status: Accepted

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

import numpy as np
import itertools
from collections import defaultdict

l   = list(range(N))
c   = 0
d   = defaultdict(list)
for i in range(1, N+1):
    for j in itertools.combinations(l, i):
        d[c] = list(j)
        c    += 1

Y = np.zeros((N, M+1), dtype=int)

for i in range(N):
    Y[i] = [int(j) for j in input().split()]

res = []
for i in range(c):
    j   = Y[d[i]].sum(0)
    if np.sum(np.r_[j[1:]] >= X) == M:
        res.append(j[0])

if len(res) > 0:
    print(min(res))
else:
    print(-1)

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools
import heapq
#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)


def main():
    n,m,x=map(int,input().split())
    c=[]
    a=[]
    for i in range(n):
        temp=list(map(int,input().split()))
        c.append(temp[0])
        a.append(temp[1:])
    total=INFI
    for i in itertools.product(range(2),repeat=n):
        tempkin=0
        rik=[0 for _ in range(m)]
        for ii in range(n):
            for iii in range(m):
                if i[ii]==1:
                    rik[iii]+=a[ii][iii]
            if i[ii]==1:
                tempkin+=c[ii]
        ans=1
        for j in range(m):
            if rik[j]<x:
                ans=0
                break
        if ans==1:
            total=min(total,tempkin)
    if total==INFI:
        print(-1)
    else:
        print(total)








if __name__ == "__main__":

    main()

Submission status: Accepted

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

for i in range(1 << N):
    tmp = [0] * M
    money = 0
    flag = True
    for j in range(N):
        if i & (1 << j):
            money += C[j]
            for k in range(M):
                tmp[k] += A[j][k]
    for j in range(M):
        if tmp[j] < X:
            flag = False
            break
    if flag:
        ans.append(money)

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

Submission status: Accepted

Solution code:
import sys
from itertools import product
def input(): return sys.stdin.readline().rstrip()

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

    ans = -1
    bit_list = list(product([0, 1], repeat=N))
    for bits in bit_list:
        tmp_ans = 0
        m_list = [0] * M

        for ca, bit in zip(CA, bits):
            if bit == 0:
                continue
            tmp_ans += ca[0]
            if ans > 0 and tmp_ans > ans:
                break
            for i, v in enumerate(ca[1:]):
                m_list[i] += v
        if min(m_list) >= X:
            if tmp_ans < ans or ans < 0:
                ans = tmp_ans
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys
from itertools import combinations

def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n, m, x = _ia()
    c = []
    a = []
    for i in range(n):
        t = list(_ia())
        c.append(t[0])
        a.append(t[1:])
    books = [i for i in range(n)]
    r = -1
    for i in range(1,n+1):
        for b in combinations(books, i):
            cost = sum(c[k] for k in b)
            if r>0 and cost>=r:
                continue
            tmp = [0] * m
            for bi in b:
                for j,aij in enumerate(a[bi]):
                    tmp[j] += aij

            if min(tmp)>=x:
                r = cost
    return r

if __name__ == "__main__":
    print(main())

Submission status: Accepted

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


def solve(flags):
    global m, c, a
    points = [0] * m
    price = 0
    for i, f in enumerate(flags):
        if f == 1:
            price += c[i]
            for j in range(m):
                points[j] += a[i][j]
    cleared = list(filter(lambda p: p >= x, points))
    return price if len(cleared) == m else -1

answer = -1
for i in range(2 ** n):
    flags = list(map(int, list(bin(i)[2:].zfill(n))))
    result = solve(flags)
    if result > 0:
        if answer == -1:
            answer = result
        else:
            answer = min(result, answer)

print(answer)

Submission status: Accepted

Solution code:
global N, M, X
N, M, X = map(int, input().split())
global C, A
C, A = [], []
for i in range(N):
    tmp, *_ = map(int, input().split())
    C.append(tmp), A.append(list(_))
    
def adde(a, b):
    t = []
    for i in range(M):
        t.append(a[i] + b[i])
    return t
        


def solve(times, big, lists, cost):
    if times == N:
        if not len(list(filter(lambda x:x<X, lists))):
            return min(big, cost)
        else:
            return big

    big = solve(times + 1, big, adde(lists, A[times]), cost + C[times])
    big = solve(times + 1, big, lists, cost)
    
    return big

ans = solve(0, float('inf'), [0 for i in range(M)], 0)
print(ans if ans != float('inf') else -1)

Submission status: Accepted

Solution code:
import itertools


n, m, x = [int(_) for _ in input().split()]
l = []
for i in range(n):
    l.append([int(_) for _ in input().split()])

# print(l)

p = []
for i in range(n):
    p.append(i)
ans = float('inf')
for i in range(1, n+1):
    for q in list(itertools.combinations(p, i)):
        flag = 0
        c = 0
        sum = [0] * m
        for j in range(len(q)):
            for k in range(m):
                # print('q[j]', q[j])
                # print('k', k)
                sum[k] += l[q[j]][k+1]
            c += l[q[j]][0]
        # print('sum', sum)
        # print('q', q)
        # print('c', c)
        for y in range(m):
            if sum[y] < x:
                flag = 1
        if flag == 0:
            ans = min(ans, c)
if ans == float('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 i in range(n)]
s = [list(map(int,bin(x)[2:].zfill(n))) for x in range(2**n)]
mi = 10000000
check = 1
for i in s:
    price=0
    a=[0]*m
    for j in range(n):
        price+=i[j]*b[j][0]
        for k in range(m):
            a[k]+=i[j]*b[j][k+1]
    for l in range(m):
        if a[l]<x:
            check=0
    if check == 1:
        mi=min(price,mi)
    check=1
if mi == 10000000:
    print("-1")
else:
    print(mi)

Submission status: Accepted

Solution code:
from itertools import product

INF = 10**10
n,m,x = map(int,input().split())
C = [0]*n
A = [[0]*m for _ in range(n)]
for i in range(n):
  T = list(map(int,input().split()))  
  C[i] = T[0]
  A[i] = T[1:]
 
prd = product([1,0],repeat = n)

ans = INF
for pr in prd:
  tmp = [0]*m
  cost = 0
  for i in range(n):
    if pr[i]:
      cost += C[i]
      for j in range(m):
        tmp[j] += A[i][j]
  if all([t>=x for t in tmp]):
    ans = min(cost,ans)
  
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


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

    for choose in range(1<<N):
        val = 0
        skill = [0] * (M+1)
        for i in range(N):
            if choose & (1 << i) != 0:
                val += books[i][0]
                for j in range(1, M+1):
                    skill[j] += books[i][j]
        accomp = True
        for j in range(1, M+1):
            if skill[j] >= X:
                continue
            else:
                accomp = False
                break
        #print("choose={}, skill={}, cost={}".format(choose, skill, val))
        if accomp:
            cost = min(cost, val)
            cost_choose = choose

    if cost == 10**10: print(-1)  
    else: print(cost)
    #print(cost_choose)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m,x = readInts()
    ans = float('inf')
    money = []
    rikai = []
    for i in range(n):
        LIST = readInts()
        money.append(LIST[0])
        rikai.append(LIST[1:])
    #print(money,rikai)
    # bit 全探索
    for bit in range(1 << n):
        mo = 0
        ansrikai = [0] * m
        for i in range(n):
            if bit & (1 << i):
                mo += money[i]
                for j in range(m):
                    ansrikai[j] += rikai[i][j]
        ok = True
        #print(ansrikai)
        for j in range(m):
            if ansrikai[j] >= x:
                ok = True
            else:
                ok = False
                break
        if ok:
            #print(ansrikai)
            ans = min(ans,mo)
    print(ans if ans != float('inf') else -1)
if __name__ == '__main__':
  main()

Submission status: Accepted

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


def main():
    N, M, X = readnums()
    ca = [list(readnums()) for _ in range(N)]
    ans = 0
    for i in range(1, 2 ** N):
        c = bin(i)[2:]
        c = '0' * (N - len(c)) + c
        tmp = 0
        tmpl = []
        for i, x in enumerate(c):
            if int(x):
                if not tmpl:
                    tmpl += ca[i]
                else:
                    tmpl = [a + b for a, b in zip(tmpl, ca[i])]

                if all([i >= X for i in tmpl[1:]]):
                    tmp = tmpl[0]
                    if not ans:
                        ans = tmp
                    else:
                        ans = min(ans, tmp)

    print(ans if ans else -1)


if __name__ == "__main__":
    main()