Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
books_info = []
price_info = []
for i in range(n):
    c, *a = map(int, input().split())
    books_info.append(a)
    price_info.append(c)
pattern_list = []
for j in range(2 ** n):
    tmp_list = []
    for k in range(n):
        if ((j >> k) & 1):
            tmp_list.append(k)
        else:
            pass
    pattern_list.append(tmp_list)
book_price = 10 ** 5 * 12 + 1
for pattern in pattern_list:
    # 全ての参考書を買わない=len(pattern)が0の場合はスキップする
    if len(pattern) == 0:
        continue
    is_ok = False
    price = 0
    for j in range(m):
        m_sum = 0
        price_sum = 0
        for k in pattern:
            m_sum += books_info[k][j]
            price_sum += price_info[k]
        if m_sum >= x:
            is_ok = True
        else:
            is_ok = False
            break
        price = price_sum
    if is_ok == True:
        book_price = min(price, book_price)
    else:
        pass
print(book_price if book_price != 10 ** 5 * 12 + 1 else -1)

Submission status: Accepted

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

for i in range(2**N):
  cost = 0
  skill = [0]*M
  cnt = 0
  for j in range(N):
    if (i>>j)&1 == 1:
      for k in range(M):
        skill[k] += CA[j][k+1]
      cost += CA[j][0]
  for l in range(M):
    if skill[l] >= X:
      cnt += 1
    if cnt == M:
      ans = min(ans,cost)
if ans == 10**9:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
#n,m,x,i,j,l,money,k,o
books = []
for i in range(n):
    books.append(list(map(int, input().split())))

ans = 10 ** 10000
import itertools
for i in range(n+1):
    for j in itertools.combinations(books, i):#j:組み合わせ
        l = [0] * m
        money = 0
        for k in j:
            money += k[0]
            for o in range(1, m + 1):
                l[o-1] += k[o]

        if all(a >=x for a in l):
            if money < ans:
                ans = money

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np

n,m,x = map(int, input().split())
A = np.array([[int(x) for x in input().split()] for i in range(n)])
lis, min_ = range(n), 1200001

full = []
#組み合わせの列挙
for r in range(1,n+1):
  comb = list(itertools.combinations(lis,r))
  full.extend(comb)
#print(full)

for i in full:
  #配列の準備
  sum_ = np.zeros(m+1)
  
  #組み合わせの要素合計
  for k in i:
    sum_+=A[k]
    #print(sum_)
    
  #Aが全てx以上もしくは最小コストか否か
  if np.all(sum_[1:]>=x) and min_>sum_[0]:
    min_ = sum_[0]

if min_== 1200001: print('-1')
else: print(int(min_))

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[list(map(int,input().split())) for i in range(N)]
INF=float("inf")
ans=INF

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

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:])
result = -1
for i in range(2 ** n):
  ct = 0
  at = [0] * m
  for b in range(0, n):
    bb = 1 << b 
    if i & bb > 0:
      ct += c[b]
      for j in range(0, m):
        at[j] += a[b][j]
  if result == -1 or ct < result:
    r = 1
    for ati in at:
      if ati < x:
        r = 0
    if r == 1:
      result = ct
print(result)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
#n,m,x,i,j,l,money,k,o
books = []
for i in range(n):
    books.append(list(map(int, input().split())))
books = sorted(books, reverse=False)
#print(books)#

ans = 10 ** 10000
import itertools
for i in range(n+1):
    for j in itertools.combinations(books, i):#j:組み合わせ
#        print(j)#
        l = [0] * m #理解度
        money = 0
        for k in j:#k:組み合わせの中の１冊
#            print(k)#
            money += k[0]  #費用
#            print(money)#
            for o in range(1, m + 1):
                l[o-1] += k[o]  #lが理解度、kが本
#        print(money,l)#
        if all(a >=x for a in l):
            if money < ans:
                ans = money

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

Submission status: Accepted

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

uds = [0]*M
cost = 0
ans = -1

for bit in range(2**N):
  for i in range(N):
    if (bit >> i) & 1:
      cost += A[i][0]
      for j in range(M):
        uds[j] += A[i][j+1]
  if min(uds) >= X:
    if ans == -1 or ans > cost:
      ans = cost
  cost = 0
  uds = [0]*M

print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ac = [list(map(int,input().split())) for _ in range(n)]
ttlmmin = 10**8
for i in range(1<<n):
    ttlm = 0
    skl = [0]*m
    for k in range(n):
        if i & (1<<k):
            for l in range(m):
                skl[l] += ac[k][l+1]
            ttlm += ac[k][0]
    flag = True
    for l in range(m):
        if skl[l] < x:
            flag = False
            break
    if flag: ttlmmin = min(ttlmmin,ttlm)    
if ttlmmin == 10**8:
    print(-1)
else:
    print(ttlmmin)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
ans=100000000000000000
for i in range(2**n):
    check=[0]*m
    ans_=0
    for j in range(n):
        if ((i>>j)&1):
            ans_+=ca[j][0]#(✳︎)
            for k in range(m):
                check[k]+=ca[j][k+1]
    if all([l>=x for l in check]):
        ans=min(ans,ans_)
if ans==100000000000000000:
    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)]

ans = float('inf')
for i in range(pow(2, N)):
    cost = 0
    x_array = [0]*M
    for j in range(N):
        if (i>>j & 1) == 1:
            cost += CA[j][0]
            for m in range(M):
                x_array[m] += CA[j][m+1]
    flag = True
    for m in range(M):
        if x_array[m] < X:
            flag = False
            break
    if flag:
        ans = min(ans, cost)

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

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**9
for i in range(2 ** n):
  skill = [0] * m
  overTen = False
  money = 0
  for j in range(n):
    if ((int(bin(i)[2:]) >> j) & 1):
      money += a[j][0]
      for h in range(m):
        skill[h] += a[j][h+1]
  for k in skill:
    if k >= x:
      overTen = True
    else:
      overTen = False
      break
  if overTen == True:
    if money < ans:
      ans = money

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

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**9 
for i in range(2 ** n):
  skill = [0] * m
  overTen = False
  money = 0
  for j in range(n):
    if ((int(bin(i)[2:]) >> j) & 1):
      money += a[j][0]
      for h in range(m):
        skill[h] += a[j][h+1]
  for k in skill:
    if k >= x:
      overTen = True
    else:
      overTen = False
      break
  if overTen == True:
    if money < ans:
      ans = money

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

Submission status: Accepted

Solution code:
import sys
def hantei(N,M,X,A,l):
  skill = [0] * M
  money = 0
  for i in range(N):
    if l[i] == '1':
      money += A[i][0]
      for j in range(M):
        skill[j] += A[i][j+1]
  for k in skill:
    if k < X:
      return -1
      sys.exit()
  return money
      
N,M,X = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
mny = 12 * (10 ** 5) + 1
for i in range(1,2**N):
  l = bin(i)[2:].zfill(N)
  if hantei(N,M,X,A,l) != -1 and hantei(N,M,X,A,l) < mny:
    mny = hantei(N,M,X,A,l)
    a = l
if mny == 12 * (10 ** 5) + 1:
  print(-1)
else:
  print(mny)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
a = [list(map(int, input().split())) for l in range(N)]
 
ans = 10**8
 
for i in range(2**N):
    score = [0] * M
    total = 0
    for j in range(N):
        if ((i >> j) & 1):
            total += a[j][0]
            for k in range(M):
                score[k] += a[j][k+1]
        
    if min(score) >= X:
        ans = min(ans, total)
 
if ans == 10**8:
    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)]
ANS=1<<60
for i in range(1<<N):
    SCORE=[0]*M
    MONEY=0
    for j in range(N):
        if (1<<j) & i != 0:
            MONEY+=B[j][0]
            for k in range(M):
                SCORE[k]+=B[j][k+1]
    if min(SCORE)>=X:
        ANS=min(ANS,MONEY)
if ANS==1<<60:
    print(-1)
else:
    print(ANS)

Submission status: Accepted

Solution code:
import itertools

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

books = []

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

patern = []

for i in range(1, n+1):
    patern += itertools.combinations(range(n), i)

cost = 10**7


for j in patern:
    total = 0
    flag = 1
    for k in range(1,m+1):
        cnt = 0
        for l in list(j):
            cnt += books[l][k]
        if cnt < x:
            flag *= 0
    if flag == 1:
        for l in j:
            total += books[l][0]
        cost = min(cost, total)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n,m,x = MI()
li = LLI(n)
ans=[]
for bit in range(1<<n):
    money = 0
    understand_li = [0]*m
    b = True
    for i in range(n):
        if ((bit >> i) & 1):
            money += li[i][0]
            for j in range(m):
              understand_li[j] += li[i][j+1]
    for k in range(m):
        if understand_li[k] < x:
            b = False
    if b == True:
        ans.append(money)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

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

ans = 0
C = []
A = []

money = [0]*2**n
moneymoney = []

for _ in range(n):
    c,*a = map(int,input().split())
    C += [c]
    A += [a]

for i in range(2**n):
    sum = [0]*m
    for j in range(n):
        if (i>>j)&1 == 1:
            for k in range(m):
                sum[k] += A[j][k]
            money[i] += C[j]
    if min(sum)>=x:
        moneymoney += [money[i]]
        
if moneymoney == []:
    ans = -1
else:
    ans = min(moneymoney)

print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
num=[]
c=[]
for i in range(n):
    c1=list(map(int,input().split()))
    c.append(c1.pop(0))
    num.append(c1)
ans=sum(c)+100
for i in range(2**n):
    num1=[0]*m
    num2=[]
    num3=0
    for j in range(n):
        if (i>>j) & 1:
            for k in range(m):
                num1[k]+=num[j][k]
            num2.append(j)
    if min(num1)>=x:
        for j in range(len(num2)):
            num3+=c[num2[j]]
        ans=min(ans,num3)
if ans==sum(c)+100:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys 
import itertools as it 

readline = sys.stdin.readline 

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

CA = []
for i in range(N):
    CA.append(readline().split())


# 理解度をX以上にする組み合わせをすべて選び、最小金額を求める
# sigma_n{C_r}は4096通り、全探索でもよさそう
arr_CA = np.array(CA, np.int64)
achieve_X = []
for select_book_num in range(N):
    for combination in it.combinations(arr_CA, select_book_num + 1): # ここまでで4096ループ
        sum = np.sum(np.array(combination, np.int64), axis=0, dtype=np.int64)    
        if sum[1:].min() >= X:
            achieve_X.append(sum)


if len(achieve_X) == 0:
    print(-1)
else:
    arr_achieve_X = np.array(achieve_X)
    print(arr_achieve_X[:, 0].min())

Submission status: Accepted

Solution code:
n,m,x = list(map(int,input().split()))
b = []
import numpy as np
for i in range(n):
    ca = list(map(int,input().split()))
    b.append(ca)
b = np.array(b)
ans = float('inf')
for i in range(1<<n):
    num = np.array([0 for j in range(m+1)])
    for k in range(n):
        if (i>>k&1)==1:
            num += b[k]
    if (num[1:]>=x).sum()==m:
        ans = min(ans, num[0])
print(ans if ans!=float('inf') else -1)

Submission status: Accepted

Solution code:
#import time

def main():
    N, M, X = map(int, input().split())
    Cs = [list(map(int, input().split())) for _ in range(N)]
    mi = 100000000000000000000 #->float("inf")
    for i in range(1<<N):
        lis = [0] * (M+1)
        for j in range(N):
            if i & (1<<j) == 0:
                continue
            for k in range(M+1):
                lis[k] += Cs[j][k]
        if all(v>=X for v in lis[1:]):
            mi = min(lis[0], mi)

    return -1 if mi == 100000000000000000000 else mi

if __name__ == '__main__':
    #start = time.time()
    print(main())
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Accepted

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

buy = []
queue = [buy]
counter = 0
min_cost = 10000000
while counter < len(queue):
    item = queue[counter]
    counter += 1
    if len(item) != N:
        for dicision in [True, False]:
            tmp = copy.copy(item)
            tmp.append(dicision)
            queue.append(tmp)
    else:
        cost = 0
        B = [0] * M
        for index, book in enumerate(item):
            if book:
                cost += C[index]
                for m in range(M):
                    B[m] += A[index][m]
        clear = True
        for b in B:
            if b < X:
                clear = False
        if clear and cost < min_cost:
            min_cost = cost

print(-1 if min_cost == 10000000 else min_cost)

Submission status: Accepted

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

c=[]

for i in range(n):
    a = [int(x) for x in input().split()]
    c.append(a)

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

ans=10**16

for j in range(1,2**n):
    b=format(j,"012b")
    b=b[::-1]
    nedan=0
    skill=[0]*m
    for k in range(n):
        if int(b[k])==1:
            nedan+=c[k][0]
            for l in range(0,m):
                skill[l]+=c[k][l+1]
    if all(goukei>=x for goukei in skill):
        ans=min(ans,nedan)

print(ans)

Submission status: Accepted

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

c=[]

for i in range(n):
    a = [int(x) for x in input().split()]
    c.append(a)

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

ans=10**16

for j in range(1,2**n):
    b=format(j,"012b")
    b=b[::-1]
    nedan=0
    skill=[0]*m
    for k in range(n):
        if int(b[k])==1:
            nedan+=c[k][0]
            for l in range(0,m):
                skill[l]+=c[k][l+1]
    if all(goukei>=x for goukei in skill):
        ans=min(ans,nedan)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
n,m,x = list(map(int, input().split()))
pa = [[] for _ in range(n)]
for i in range(n):
  pa[i] = list(map(int, input().split()))
  
pa = np.array(pa)
ans = 10**5 * n + 1

for i in range(1,n+1):
  for cs in list(combinations(range(n),i)):
    p = np.array([0]*(m+1))
    for j in cs:
      p += pa[j]
    if min(p[1:]) >= x:
      ans = min(ans, p[0])

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
book=[list(map(int,input().split())) for i in range(n)]
ans=10**7
for i in range(2**n):
    l=[0]*(m+1)
    for j in range(n):
        if (i>>j&1):
            for k in range(m+1):
                l[k]+=book[j][k]
        if all(l[i]>=x for i in range(1,m+1)):
            if l[0]<ans:
                ans=l[0]
if ans==10**7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

for hon in(itertools.product([0,1], repeat=n)):
  hoge=list(hon)
  #print(hoge)
  rikai=[0 for i in range(m+1)]
  for i in range(n):
    if(hoge[i]==1):
      for j in  range(m+1):
        rikai[j]+=book[i][j]
  #print(rikai)
  money=rikai[0]
  rikai=rikai[1:]
  if(min(rikai)>=x):
    if(ans==-1):
      ans=money
    else:
      ans=min(ans,money)
      
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


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


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

    v = []
    for _ in range(N):
        l = list(map(int, input().split()))
        v.append(l)

    ans = INF
    for b in range(2**N):
        cost = 0
        r = [0] * M
        for i in range(N):
            if (b >> i) & 1:
                cost += v[i][0]
                for j in range(1, M + 1):
                    r[j - 1] += v[i][j]

        ok = True
        for j in range(M):
            ok &= r[j] >= X
        if ok:
            ans = min(ans, cost)

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


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

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

c = []
ans = pow(10, 9)

for i in range(n):
    c.append(list(map(int, input().split())))
for mask in range((1 << n) - 1):
    sum = 0
    li = [0] * m
    for i in range(n):
        if (mask >> i) & 1 == 0:
            sum += c[i][0]
            for j in range(m):
                li[j] += c[i][j+1]
    check = True
    for j in range(m):
        if li[j] < x:
            check = False
            break
    if check:
        ans = min(sum, ans)

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

Submission status: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    12th july , 2020  - Sunday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================

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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) : # Check Prime Number or not
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
def bfs(g,st,lcatable,level):
    visited = [0]*(len(g))
    visited[st] = 1
    queue = []
    queue.append(st)
    new = []
    while(len(queue) != 0):
        s = queue.pop()
        new.append(s)
        for i in g[s]:
            if(visited[i] == 0):
                level[i] = level[s]+1
                lcatable[i][0] = s
                visited[i] = 1
                queue.append(i)

    return new

def lcatable(g,n,level): #O(nlogn) make table beforehand.to answer per query in O(logn)
    mx = 0
    while(2**(mx) <=n):
        mx+=1
    # print('mx',mx)
    lcatable = [[-1]*mx for i in range(n+1)]
    bfs(g,1,lcatable,level)

    for j in range(1,mx):
        for i in range(1,n+1):
            if(lcatable[i][j-1] != -1):
                lcatable[i][j] = lcatable[lcatable[i][j-1]][j-1]

    return lcatable

def dist(x0,y0,x1,y1):
    return (abs(x0-x1) + abs(y0-y1))

def djkistra(g,st,dist): #g contains b,dist(a to b) and dist is initiaalised by 10**9 initiallly
    pq = []
    dist[st] = 0
    pq.append([0,st])
    while(len(pq) != 0):
        curr = heappop(pq)[1]
        for i in range(0,len(g[curr])):
            b = g[curr][i][0]
            w = g[curr][i][1]
            if(dist[b] > dist[curr] + w):
                dist[b] = dist[curr]+w
                pq.append([dist[b],b])
    return dist

# ini = 10**5
def solve():
    N,M,X = sep()
    C =[]
    A = []
    for _ in range(N):
        temp = list(map(int, input().split()))
        C.append(temp[0])
        A.append(temp[1:])

    res = []

    for a in product((0,1), repeat=N):
        P = [0] * M
        cost = 0
        for i in range(N):
            if a[i]:
                cost += C[i]
                for j in range(M):
                    P[j] += A[i][j]
        for j in range(M):
            if P[j] < X:
                break
            if j == M-1:
                res.append(cost)

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

testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
import numpy as np
import sys
n,m,x = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
#print(a)
mi = sys.maxsize
flag = False
for i in range(2**n):
    b = np.array([0]*(m+1))
    f = True
    for k in range(n):
        if i>>k&1:
            b += np.array(a[k])
    for j in range(1,m+1):
        if b[j] < x:
            f = False
    if f:
        flag = True
        mi = min(mi,b[0])
if flag:
    print(mi) 
else:
    print(-1)

Submission status: Accepted

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

ans = sum(C)+1
for i in range(1 << N):
    Q = [0] * M
    price = 0
    bits = format(i, 'b')
    for j in range(N):
        if i & (1 << j):
            for k in range(M):
                Q[k] += A[j][k]
            price += C[j]

    flg = True
    for j in range(M):
        if Q[j] < X:
            flg = False
    if flg:
        ans = min(ans, price)
print(ans if ans < sum(C) + 1 else -1)

Submission status: Accepted

Solution code:
n,m,d=map(int,input().split())
INF=10**18
c=[0]*n
a=[]
for i in range(n):
  c[i],*b=list(map(int,input().split()))
  a.append(b)
ans=INF
for i in range(2**n):
  x=[0]*m
  cnt=0
  for j in range(n):
    if (i>>j)&1:
      cnt+=c[j]
      for k in range(m):
        x[k]+=a[j][k]
  for j in range(m):
    if x[j]<d:break
  else:ans=min(cnt,ans)
print(ans if ans!=INF else -1)

Submission status: Accepted

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

ok = 0
min_price = 12 * 10 ** 5
for i in range(2 ** n):
    skills = [0] * m
    price = 0
    for j in range(n):
        if i >> j & 1:
            price += ca[j][0]
            for k in range(m):
                skills[k] += ca[j][k + 1]
    if all([j >= x for j in skills]):
        min_price = min(price, min_price)
        ok = 1
if ok:
    print(min_price)
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import product
N,M,X = map(int,input().split())
cc = [list(map(int,input().split())) for i in range(N)]
saisyou = float('inf')
for i in product([0,1],repeat=N):
  dd = [0]*(M+1)
  check = 0
  for j in range(N):
    if i[j] == 1:
      for h in range(M+1):
        dd[h] += cc[j][h]
  for k in dd[1:]:
    if k < X:
      check = 1
  if check == 0:
    saisyou = min(dd[0],saisyou)
if saisyou == float('inf'):
  saisyou = -1
print(saisyou)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
for _ in range(n):
  s=list(map(int,input().split()))
  a.append(s)
  
ans=[]
check=0
for q in range(2**n):
  nedan=[0]*m
  sum1=0
  for i in range(n):
    if ((q>>i) &1):
      sum1+=a[i][0]
      for p in range(m):
        nedan[p]+=a[i][p+1]
  
  t=min(nedan)
  if t>=x  :
    ans.append(sum1)
    check+=1
    
if check==0:
  print(-1)
  
else:
  print(min(ans))

Submission status: Accepted

Solution code:
n,m,x = list(map(int,input().split()))
ca = []
ans = -1

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

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

print(ans)