Problem:


Score : 300 points

Problem

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

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

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

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

120

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

Sample Input 2

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

Sample Output 2

-1

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

Sample Input 3

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

Sample Output 3

1067



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


Sample output:
120

Submission status: Accepted

Solution code:

def main():
    N, M, X = map(int,input().split())
    
    cost = []
    effect = []
    for _ in range(N):
        t = list(map(int,input().split()))
        cost.append(t[0])
        effect.append(t[1:])

    res = float("inf")
    for bits in range(1<<N):
        f = True
        total = 0
        ans = [0] * M
        for flag in range(N):
            if (1<< flag) & (bits):
                total += cost[flag]
                for idx, e in enumerate(effect[flag]):
                    ans[idx] += e 
        for a in ans:
            if a < X: f = False
        if f:
            res = min(res, total)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#ABC167
N,M,X=map(int,input().split())
c = []  #参考書の値段
a = []  #各参考書に入る理解度
for i in range(N):
    c_temp, *a_temp = list(map(int, input().split()))  # こうすると、2つ目以降をリストで受け取れる
    c.append(c_temp)
    a.append(a_temp)
price_min = 10000000
for i in range(2**N):
    price_total = 0  #値段の合計
    learn_total = [0] * M #理解度の合計
    for j in range(N):
        if (i >> j) & 1:  # j桁目が0か1か見て、j冊目を買うか買わないか判定します
            price_total += c[j]  # 買うので、j冊目の値段を加算します
            learn = a[j]  # 「j冊目の参考書を読んで増える、各アルゴリズムの理解度」のリストです
            for k, la in enumerate(learn):  # 理解度を加算します enumerateを使うと、range(n)よりスマートです
                learn_total[k] += la
    if all(learn_total[k] >= X for k in range(M)):
        if price_min > price_total:
            price_min=price_total
            
if price_min==10000000:
    print (-1)
else:
    print (price_min)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 1000000007

n, m, x = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()]for j in range(n)]    # nは行数

tmp = 0
res = inf

for i in range(2 ** n):
    s = f"{i:0{n}b}"
    tmp = [0 for i in range(m + 1)]
    for j in range(n):
        if s[j] == "1":
            for k in range(m + 1):
                tmp[k] += A[j][k]
    flg = True
    for k in range(1, m + 1):
        if tmp[k] < x:
            flg = False
    if flg:
        res = min(res, tmp[0])
if res == inf:
    res = -1

print(res)

Submission status: Accepted

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

# 入力をすべて受け取る
for i in range(n):
  tmp = list(map(int, input().split()))
  inp.append(tmp)

# bit全探索を行うための箱づくり
sum = 0
min = 10**10
for i in range(2**n):
  tmp = [0]*m
  flg = 0
  
  # ある買う買わないのケースに対して、フラグが立ってたらスキルポイントを増やす
  for j in range(n):
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      sum += inp[j][0]
      for k in range(1,m+1):
        #print(n,j, k, tmp, inp)
        tmp[k-1] += inp[j][k]
  for ii, k in enumerate(tmp):
    if k < x: # x未満ならflgをたててNGとする
      flg = 1
      break
  #print(tmp, flg)
  if sum < min and flg == 0: min = sum
  sum = 0
  
if min == 10**10: min = -1
print(min)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

ans = -1
for i in range(1<<N):
    bit = [0] * N
    for j in range(N):
        div = 1 << j
        bit[j] = (i // div) % 2

    res = [0] * M
    cost = 0
    for n in range(N):
        if bit[n]==0:
            continue
        cost += CA[n][0]
        for m in range(1,M+1):
            res[m-1] += CA[n][m]

    flag = True
    for m in range(M):
        if res[m] < X:
            flag = False
            break
    
    if flag:
        if ans == -1:
            ans = cost
        else:
            ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
def main():
    N,M,X = map(int,input().split())
    ca = [list(map(int,input().split())) for _ in range(N)]
    
    mincost = 12*10**5
    flag = 0
    for i in range(1,2**N):
        lev = [0] * M
        cost = 0
        a = list((("0"*N)+bin(i)[2:])[-N:])
        for j in range(N):
            if a[j] == "1":
                cost +=  ca[j][0]
                for k in range(M):
                    lev[k] += ca[j][k+1]
        if min(lev) >= X:
            mincost = min(mincost,cost)
            flag = 1
    if flag == 0:
        print(-1)
    else:
        print(mincost)
main()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
a = []
c = []
for i in range(n):
  a.append(list(map(int,input().split())))
  c.append(a[i])
  
p = []
for i in range(2 ** (n)):
    tmp = [0] * (n)
    for j in range(n):
        if i >> j & 1:
            tmp[j] = 1
    p.append(tmp)
ans = []

for i in range(len(p)):
  tmp = 0
  tmp2 = [0]*m
  tmp3 = 0
  for j in range(len(p[i])):
    if p[i][j] == 1:
      tmp += a[j][0]
      for k in range(m):
        tmp2[k] += a[j][k+1]
  for k in range(m):
    if tmp2[k] >= x:
      tmp3 += 1
  if tmp3 == m:
    ans.append(tmp)
  #print(tmp2)
  
if len(ans) == 0:
  print(-1)
else:
  print(min(ans))

Submission status: Accepted

Solution code:
n, m, x = map(int,input().split())
lst = [[0 for i in range(m + 1)]]
for i in range(n):
    tmp = list(map(int,input().split()))
    for j in range(len(lst)):
        tmp2 = []
        for k in range(len(tmp)):
            y = lst[j][k] + tmp[k]
            tmp2.append(y)
        lst.append(tmp2)
ans = -1
for i in range(len(lst)):
    c = 0
    for j in range(len(lst[i])):
        if (j == 0):
            pass
        else:
            if (lst[i][j] < x):
                c = 1
    if (c == 0):
        if (ans == -1):
            ans = lst[i][0]
        else:
            ans = min(ans, lst[i][0])

print(ans)

Submission status: Accepted

Solution code:
N, M, X = [int(i) for i in input().split()]
CA = []
for i in range(N):
    CA.append([int(j) for j in input().split()])
#print(CA)
mcost = 10**10


for i in range(2**N):
    learn = [0]*M
    cost = 0
    bn = str(bin(i))[2:].zfill(N)
    #print(bn)
    for j,b in enumerate(bn):
        if b == "1":
            cost += CA[j][0]
            for m in range(M):
                learn[m] += CA[j][m+1]
                
    learn.sort()
    #print(learn)
    if learn[0] >= X:
        mcost = min(mcost, cost)

if mcost == 10**10:
    mcost = -1

print(mcost)

Submission status: Accepted

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

# 入力をすべて受け取る
for i in range(n):
  tmp = list(map(int, input().split()))
  inp.append(tmp)

# bit全探索を行うための箱づくり
sum = 0
min = 10**10
for i in range(2**n):
  tmp = [0]*m
  flg = 0
  
  # ある買う買わないのケースに対して、フラグが立ってたらスキルポイントを増やす
  for j in range(n):
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      sum += inp[j][0]
      for k in range(1,m+1):
        #print(n,j, k, tmp, inp)
        tmp[k-1] += inp[j][k]
  for ii, k in enumerate(tmp):
    if k < x: # x未満ならflgをたててNGとする
      flg = 1
      break
  #print(tmp, flg)
  if sum < min and flg == 0: min = sum
  sum = 0
  
if min == 10**10: min = -1
print(min)

Submission status: Accepted

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

c = []
a = []

for i in range(n):
    c.append(ca[i][0])
    a.append(ca[i][1:])

INF = 10**9
ans = INF

for i in range(1 << n):
    sum_cost = 0
    skill = [0]*m
    for j in range(n):
        if (i >> j)&1:
            sum_cost += c[j]
            for k in range(m):
                skill[k] += a[j][k]
    check_cnt = 0
    for l in range(m):
        if skill[l] >= x:
            check_cnt += 1
    if check_cnt == m:
        ans = min(ans,sum_cost)

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

Submission status: Accepted

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

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

INF = 10**9 + 7
minpr = INF
for i in range(2**N):
    buy = list()
    for j in range(N):
        if i&1==1: buy.append(j)
        i >>= 1
    skill = [0]*M
    price = 0
    for k in range(len(buy)):
        price += C[buy[k]][0]
        for l in range(M):
            skill[l] += C[buy[k]][l+1]
    for m in range(M):
        if skill[m] < X: break
    else:
        if minpr > price: minpr = price
if minpr==INF:
    print(-1)
else:
    print(minpr)

Submission status: Accepted

Solution code:

url = "https://atcoder.jp//contests/abc160/tasks/abc160_c"

import itertools


def main():
    n, m , X = list(map(int, input().split()))
    books = []
    ans = -1
    for _ in range(n):
        books.append(list(map(int, input().split())))
    for i in range(n):
        for row in itertools.combinations(range(0, n), i+1):
            cost = 0
            rikai = [0] * m
            for idx in row:
                cost += books[idx][0]
                for idx2 in range(1, len(books[idx])):
                    rikai[idx2 - 1] += books[idx][idx2]
                if len(list(filter(lambda x: x >= X, rikai))) == len(rikai):
                    ans = min(ans, cost) if ans != -1 else cost
    print(ans)








if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
a=2**N
J=[]
for i in range(a):
    T=True
    K=[0]*(M+1)
    for j in range(N):
        if (i>>j)&1:
            for k in range(M+1):
                K[k]+=L[j][k]
    for j in range(1,M+1):
        if K[j]<X:
            T=False
    if T:
        J.append(K[0])
if len(J)==0:
    print(-1)
else:
    J.sort()
    print(J[0])

Submission status: Accepted

Solution code:
import numpy as np
import itertools

def check():
    N,M,X = map(int, input().split())
    A = np.array([[int(i) for i in input().split()] for _ in range(N)])
    total = np.sum(A,axis=0)
    flag = True if all((a>=X  for a in total[1:])) else False
    ans = total[0]

    if flag:
        for i in range(1,N+1):
            for v in itertools.combinations([i for i in range(N)], i):
                B = np.array([A[j] for j in v])
                total2 = np.sum(B, axis=0)
                sabun = total-total2
                if all(a>=X for a in sabun[1:]):
                    ans = min(ans, sabun[0])
    print(ans if flag else -1)
    
check()

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 10**10
for l in product([False, True], repeat=N):
    for i in range(M):
        if sum(ca[i+1] for j, ca in enumerate(CA) if l[j]) < X:
            break
    else:
        s = sum(ca[0] for j, ca in enumerate(CA) if l[j])
        ans = min(ans, s)
print(-1 if ans == 10**10 else ans)

Submission status: Accepted

Solution code:
from itertools import product

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

cost = -1
for cand in product((0, 1), repeat=n):
  tmp = 0
  scores = [0] * m
  for bought, ca in zip(cand, CA):
    if not bought:
      continue
    for i in range(1, m + 1):
      scores[i - 1] += ca[i]
    tmp +=  ca[0]
  if min(scores) >= x and (cost == -1 or tmp < cost):
    cost = tmp
print(cost)

Submission status: Accepted

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

ans=float('inf')
for i in range(2**n):
  data=[0]*(m+1)
  for j in range(n):
    if i&(1<<j):
      for k in range(m+1):
        data[k]+=c[j][k]
    cnt=0
    for l in range(1,m+1):
      if data[l]>=x:
        cnt+=1
    if cnt==m:
      ans=min(ans,data[0])
if ans==float('inf'):
  print(-1)
  exit()
print(ans)

Submission status: Accepted

Solution code:
N,M,X=[int(s) for s in input().split()]
Book=[[int(s) for s in input().split()] for _ in range(N)]
INF=10**7

ans=set()
ans.add(INF)
#深さ優先探索
def DFS(n,cost,Xls):
  if n==N:
    if min(Xls)>=X:
      ans.add(cost)
  else:
    Xnext=[Xls[i]+Book[n][i+1] for i in range(M)]
    DFS(n+1,cost+Book[n][0],Xnext)
    DFS(n+1,cost,Xls)

DFS(0,0,[0 for _ in range(M)])
if min(ans)==INF:
  print(-1)
else:
  print(min(ans))

Submission status: Accepted

Solution code:
N,M,X=[int(s) for s in input().split()]
Book=[[int(s) for s in input().split()] for _ in range(N)]
INF=10**7

ans=set()
ans.add(INF)

for n in range(2**N):
  #Bit全探索
  Xls=[0 for i in range(M)]
  cost=0
  for i in range(N):
    if ((n>>i)&1)==1:
      cost+=Book[i][0]
      for b in range(M):
        Xls[b]+=Book[i][b+1]
    if min(Xls)>=X:
      ans.add(cost)
if min(ans)==INF:
  print(-1)
else:
  print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = list(map(int,input().split()))
c = []
a = []

for i in range(n):
  stdIn = list(map(int,input().split()))
  c.append(stdIn[0])
  a.append(stdIn[1:])
flag = 0
ans = sum(c)
for i in range(2**n):
  result = np.array([0]*m)
  price = 0
  for j in range(n):
    if((i>>j)&1):
      result += a[j]
      price += c[j]
  if (len(result[result<x])==0):
    ans = min(ans,price)
    flag = 1
print(ans if flag != 0 else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
books = [list(map(int,input().split())) for _ in range(n)]
ans = 12 * (10**5) + 1
for i in range(2**n):
    kingaku = 0
    rikaido = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            kingaku += books[j][0]
            for k in range(m):
                rikaido[k] += books[j][k+1]
    if all((a >= x for a in rikaido)):
        ans = min(ans,kingaku)
if ans != 12 * (10**5) + 1:
    print(ans)
else:
    print("-1")

Submission status: Accepted

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

sum = 0
for i in range(n):
    sum += ca[i][0]
ans = sum + 1

for i in range(2**n) :
    cnt = 0
    a = [0]*m
    for j in range(n) :
        if ((i>>j)&1) :
            for k in range(m) :
                a[k] += ca[j][k+1]
            cnt += ca[j][0]
    if cnt > 0 and min(a) >= x :
        ans = min(cnt,ans)

if ans == sum + 1 :
    print(-1)
else :
    print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
import copy

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

ans = 10 ** 7
for i in itertools.product([0, 1], repeat=N):
    tCA = copy.copy(CA)
    for j in range(N):
        if i[j] == 0:
            tCA[j] = np.zeros(CA.shape[1])
    s = np.sum(tCA, axis=0)
    l = sum(k >= X for k in s[1:])
    if s[0] < ans and l == M:
        ans = s[0]

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':

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

    A = []
    for i in range(n):
        cmd = list(map(int,input().split()))
        A.append(cmd)
    #bit全探索 買う・買わないを判断する
    INF = 10**19
    ans = INF
    for x in range(2**n):
        ALG = [0]*m
        gokei = 0
        for y in range(n):
            if (x>>y) & 1:
                #取得する配列が決まったら、アルゴリズム理解度を＋していく
                for j in range(m):
                    ALG[j] += A[y][j+1]
                gokei += A[y][0]
        #Alg配列の中身がすべて理解度xを超えているかのチェック
        algflg=True
        for k in ALG:
            if k < a:
                algflg=False
                break
        if algflg:
            ans = min(ans,gokei)
    if ans == INF:
        print("-1")
    else:
        print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m, x = map(int, input().split())
    sofar = 10 ** 5 + 1
    cl = list(list(map(int, input().split())) for _ in range(n))
    # print(cl)
    ans = float('inf')
    for i in range(2 ** n):
        tmp = [0] * m
        cost = 0
        for j in range(n):
            # print(bin(j), i, bin(i >> j))
            if (i >> j) & 1:
                for k in range(m):
                    tmp[k] += cl[j][k + 1]
                cost += cl[j][0]
                # print(tmp)
        for t in tmp:
            if t < x:
                break
        else:
            ans = min(ans, cost)
    if ans == float('inf'):
        return -1
    else:
        return ans


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

Submission status: Accepted

Solution code:
import numpy as np


def main() -> None:
    n, m, x = map(int, input().split())
    books = [tuple(map(int, input().split())) for _ in range(n)]

    is_able = False
    answer = float('inf')
    for i in range(2**n):
        money = 0
        skills = np.zeros(m)
        for j in range(n):
            if ((i >> j) & 1):
                money += books[j][0]
                skills += books[j][1:]
        if x <= skills.min():
            is_able = True
            answer = min(answer, money)

    print(answer if is_able else -1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#他の人の回答
n, m, x = map(int, input().split())
ca = [list(map(int,input().split())) for _ in range(n)]

add = []

for i in range(2**n):
    skill = [0]*(m+1)
    for j in range(n):
        if ((i>>j) & 1):
            skill = list(map(sum, zip(skill, ca[j])))
    if min(skill[1:])>=x:
        add.append(skill)

if add:
    add.sort()
    print(add[0][0])
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int, input().split())
li = []
for i in range(n):
    c_A = list(map(int, input().split()))
    li.append(c_A)

li = np.array(li)
cost = 10**7
for i in range(2**n):
    c_s = np.array([0]*(m+1))
    for j in range(n):
        if ((i>>j)&1):
            c_s += li[j]
    if np.all(c_s[1:]>=x):
        cost = min(cost,c_s[0])
if cost==10**7:
    print(-1)
else:
    print(cost)

Submission status: Accepted

Solution code:
n,m,r = map(int,input().split())
books = [[int(i) for i in input().split()] for _ in range(n)]
t = []

for x in range(2**n):
    p = [0]*(m+1)
    for y in range(n):
        if (x>>y)&1 :
            p = [a+b for (a,b) in zip(books[y],p)]
    t.append(p)




ans = []


c = True

for z in t:
    c = True
    for s in range(1,m+1):
        if z[s] < r:
            c = False
    if c:
        ans.append(z[0])

if ans != []:
    print(min(ans))

else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = list(map(int, input().split()))
A = [0]*N

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

min_sump = -1
for i in range(2**(N+1)):
    sump = 0
    sume = [0]*M
    for j in range(N):
        ns = "0" + str(N) +"b"
        bi = format(i,ns)
        if bi[-1-j] == "1":
            sump += A[j][0]
            sume = list(map(sum, zip(sume, A[j][1:])))
    if all([i >= X for i in sume]):
        if min_sump == -1:
            min_sump = sump
        else:
            min_sump = min(min_sump,sump)

print(min_sump)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ca = [[0]]*n
for i in range(n):
  ca[i] = list(map(int,input().split()))
minc = 10**10
for b in range(2**n):
  r = [0]*m
  c = 0
  for i in range(n):
    if b & (1<<i)>0:
      c += ca[i][0]
      for j in range(m):
        r[j] += ca[i][j+1]
  flag = True
  for j in range(m):
    if r[j] < x:
      flag = False
  if flag:
    minc=min(c,minc)
if minc < 10**9:
  print(minc)
else:
  print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = float('INF')
for i in range(1,N+1):
    for li in combinations(list(range(N)), i):
        cost = 0
        skill = [0] * M
        for j in li:
            cost += C[j]
            for k in range(M):
                skill[k] += A[j][k]
        if all([s >= X for s in skill]):
            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())
cl = list(list(map(int, input().split())) for _ in range(n))

ans = float('inf')
for i in range(2**n):
    tmp = [0]*m
    cost = 0
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                tmp[k] += cl[j][k+1]
            cost += cl[j][0]
    for t in tmp:
        if t < x:
            break
    else:
        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())
C = []
A = []

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

ans = -1

for i in range(1, 1 << N):
    price = 0
    skill = [0] * M
    b = len(bin(i)) - 2
    for j in range(b):
        price += C[j] * (i >> j & 1)
        for k in range(M):
            skill[k] += A[j][k] * (i >> j & 1)

    if min(skill) >= X and (price < ans or ans < 0):
        ans = price

print(ans)

Submission status: Accepted

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

for i in range(2**n):
    a = [0]*m
    cnt = 0
    for j in range(n):
        if i>>j & 1:
            for k in range(1, m+1):
                a[k-1] += ll[j][k]
            cnt += ll[j][0]
    if all(s >= x for s in a):
        ans = min(ans, cnt)
print(ans if ans < 10**9 else -1)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int, input().split())
costs = []
understnding = []
ans = 10 ** 20

for _ in range(n):
    tmp = list(map(int, input().split()))
    costs.append(tmp[0])
    understnding.append(tmp[1:])
    
costs = np.array(costs)
understnding = np.array(understnding)

for i in range(1, 2**n):
    row = str(bin(i)).split("0b")[1]
    row = '0'*(n - len(row))+row
    one_index = [j for j in range(len(row)) if row[j] =="1"]
    cost_sum = np.sum(costs[one_index])
    under_sum = np.sum(understnding[one_index], axis=0)
    if np.all(under_sum >= x) and cost_sum < ans:
        ans = cost_sum
    
if ans == 10 ** 20:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
n,m,x = map(int, input().split())
costs = []
understnding = []
ans = 10 ** 20

for _ in range(n):
    tmp = list(map(int, input().split()))
    costs.append(tmp[0])
    understnding.append(tmp[1:])
    
costs = np.array(costs)
understnding = np.array(understnding)

for i in range(1, 2**n):
    row = str(bin(i)).split("0b")[1]
    row = '0'*(n - len(row))+row
    one_index = [j for j in range(len(row)) if row[j] =="1"]
    cost_sum = np.sum(costs[one_index])
    under_sum = np.sum(understnding[one_index], axis=0)
    if np.all(under_sum >= x) and cost_sum < ans:
        ans = cost_sum
    
if ans == 10 ** 20:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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

ans=-1
for i in range(1<<N):     #range(0,2^N)　左ビットシフト
    A_sum=[0]*M             #t=[0 0 0]など len(t)=M
    C_sum=0
    for j in range(N):
        if (i>>j)&1==0:   #jのフラグがないとき
            continue
        C_sum+=C[j]               #合計の値段
        for k in range(M):
            A_sum[k]+=A[j][k]     #合計の理解度  
    if all(x>=X for x in A_sum):  #tのすべての要素がXより大きいとき
        if ans==-1:
            ans=C_sum
        else:
            ans=min(ans,C_sum)
print(ans)

Submission status: Accepted

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

x = 2**N + 1
ans_candidate = []
valid = False
ans += 1
ans_old = ans
for i in range(x):
    if i != 0:
        for l in range(len(sum)):
            if sum[l] >= X and l == len(sum) -1:
                valid = True
            if sum[l] >= X:
                continue
            else:
                valid = False
                break
        if valid and price < ans:
            ans = price
    sum = [0] * M
    price = 0
    for j in range(N):
        if i >> j & 1 == 1:
            price += data[j][0]
            for k in range(M):
                sum[k] += data[j][k+1]

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

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


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


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')

import numpy as np

def main():
	n,m,x=MI()
	C=[]
	A=[]
	for _ in range(n):
		c_,*A_=LI()
		C.append(c_)
		A.append(A_)
	A=np.array(A)
	
	ans=10**10
	
	for i in range(1<<n):
		B=np.zeros(m)
		cnt=0
		for j in range(n):
			if 1<<j&i:
				cnt+=C[j]
				B+=A[j]
		if np.min(B)>=x:
			ans=min(ans,cnt)
	print(ans if ans!=10**10 else -1)
	





if __name__=="__main__":
	main()

Submission status: Accepted

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

x=N*10**10
sum_ok = N*10**10
unst =[0]*M
flg=0

def all0(v):
    return 0


for i in range(2**N):
    # print(bin(i))
    sum = 0
    unst = list(map(all0,unst))
    for j in range(N):
        if (i >> j) & 1 :
            # print(j)
            sum += B[j][0]
            # unst = list(map(lamda:x,x+B[j][]))
            for k in range(M):
                unst[k]+=B[j][k+1]
    # print(unst)
    # print("sum=",sum)
    if all(elem >= X for elem in unst):
        sum_ok = sum
        flg=1
    x=min(x,sum_ok)
    # print(x)
        
# print(unst)

if flg==0:
    print(-1)
else:
    print(x)

Submission status: Accepted

Solution code:
import numpy as np
N,M,X=map(int,input().split())
C=[[0 for i in range(M)] for j in range(N)]
for i in range(N):
    C[i] = list(map(int, input().split()))
D=np.array(C)
E=[0]*2**N

for i in range(2**N):
  c=format(i,'012b')
  for j in range(N):
    d=int(c[12-N+j])
    E[i]+=D[j]*int(d)

if min(E[-1][1:M+1])<X:
  print(-1);exit()
    
Max=E[-1][0]+1
Min=Max
for i in range(2**N):
  if min(E[i][1:M+1])>=X:
    if Min>E[i][0]:Min=E[i][0]
    continue
  else:E[i][0]=Max
print(Min)
exit()

Submission status: Accepted

Solution code:
import numpy as np
N,M,X=map(int,input().split())
  
C=[[0 for i in range(M)] for j in range(N)]
for i in range(N):
    #C=[[0 for i in range(M)] for j in range(2**N)]
    C[i] = list(map(int, input().split()))
    #print(array)
    #np.insert(C[i],0,array)
D=np.array(C)
E=[0]*2**N

for i in range(2**N):
  c=format(i,'012b')
  for j in range(N):
    d=int(c[12-N+j])
    E[i]+=D[j]*int(d)
#print(E)

#for i in range(2**M):
if min(E[-1][1:M+1])<X:
  print(-1);exit()
    
Max=E[-1][0]+1
Min=Max
for i in range(2**N):
  if min(E[i][1:M+1])>=X:
    if Min>E[i][0]:Min=E[i][0]
    continue
  else:E[i][0]=Max
#print(E)
print(Min)
exit()

Submission status: Accepted

Solution code:
#
# abc167 c
#
import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)


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

    ans = float("inf")
    for bit in range(1 << N):
        S = [0]*(M+1)
        for i, ca in enumerate(CA):
            if (1 << i) & bit == 1 << i:
                S = list(map(sum, zip(S, ca)))
        if min(S[1:]) >= X:
            ans = min(ans, S[0])

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

    print(ans)


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

    b = deque()
    ans = dfs(0, b)
    if ans == float("inf"):
        ans = -1

    print(ans)


def dfs(n, B):
    if n == N:
        S = [0]*(M+1)
        for i, ca in enumerate(CA, 1):
            if i in B:
                S = list(map(sum, zip(S, ca)))
        if min(S[1:]) < X:
            return float("inf")
        else:
            return S[0]

    ans = float("inf")
    B.append(n+1)
    ans = min(ans, dfs(n+1, B))
    B.pop()
    ans = min(ans, dfs(n+1, B))

    return ans


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

from itertools import combinations

costs =[]
for i in range(1,N+1):
    idx = list(range(N))
    comb = list(combinations(idx,i))
    for c in comb:
        scores = [0]*M
        cost = 0
        for j in c:
            cost += C[j]
            for m in range(M):
                scores[m] += A[j][m]

            check = [int(s>=X) for s in scores]

            if sum(check)==M:
                costs.append(cost)

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