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())
l = []
for _ in range(n):
    temp = list(map(int, input().split()))
    l.append(temp)

ans = 99999999

for i in range(2 ** n):
    bag = []
    for j in range(n):  # bit全探索
        if (i >> j) & 1:
            bag.append(l[j])
    skill = [0] * m
    enough = [0] * m  # 各スキルにつき、xを超えているかどうかを判断
    cost = 0
    for sub in bag:
        cost += sub[0]
        for kk in range(1, m+1):
            skill[kk - 1] += sub[kk]
            if skill[kk - 1] >= x:
                enough[kk - 1] += 1
    if 0 not in enough:  # すべてのスキルがxを超えていたら価格を計算
        if ans > cost:
            ans = cost  # 最低価格を下回っていたら更新
if ans == 99999999:  # 初期値からの変更がなければ-1を、そうでなければ最低価格を出力
    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:])
  
result = -1
for i in range(1 << n):
  t = [0] * m
  c = 0
  for j in range(n):
    if (i >> j) & 1 == 0:
      continue
    c += C[j]
    for k in range(m):
      t[k] += A[j][k]
  if all(z >= x for z in t):
    if result == -1:
      result = c
    else:
      result = min(result, c)
print(result)

Submission status: Accepted

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

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

    flag = False
    ans = 10 ** 18

    for i in range(1<<N):
        tmp = [0] * (M+1)
        mflag = True
        for j in range(N):
            if (i>>j)&1:
                tmp = [x+y for x, y in zip(tmp, mat[j])]
        for k in range(M):
            if tmp[1+k] < X:
                mflag = False
                break
        if mflag and tmp[0] < ans:
            ans = tmp[0]
            flag = True
    print(ans) if flag else print('-1')

if __name__ == '__main__':
    main()

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


result = -1
for i in range(2**n):
  skill = [0]*m
  cost = 0
  for j in range(n):
    if (i >> j) & 1 == 0:
      continue
    cost += c[j]
    for s in range(m):
      skill[s] += a[j][s]

  if all(s >= x for s in skill):
    if result == -1:
      result = cost
    else:
      result = min(result,cost)
print(result)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for _ in range(n)]
a,c=np.array([i[1:] for i in ca]).T,np.array([i[0] for i in ca])
ans=pow(10,9)
for i in product([0,1],repeat=n):
  i=np.array(i)
  if all(np.dot(a,i)>=x):
    s=np.dot(i,c)
    ans=s if s<ans else ans
print(ans if ans<pow(10,9) else -1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
sankosho = []
for n in range(N):
    input_data = list(map(int, input().split()))
    sankosho.append(input_data)
for j in range(1, M+1):
    summed = 0
    for i in range(N):
        summed += sankosho[i][j]
    if summed < X:
        print(-1)
        exit()
ans_opt = []
for bit in range(2**N):
    cost = 0
    gain = []
    for i in range(N):
        if ((bit >> i) & 1):
            cost += sankosho[i][0]
            for j in range(1, M+1):
                if len(gain) <= j-1:
                    gain.append(sankosho[i][j])
                else:
                    gain[j-1] += sankosho[i][j]
    if not(len(gain) == 0):
        if min(gain) >= X:
            ans_opt.append(cost)
print(min(ans_opt))

Submission status: Accepted

Solution code:
#167
N,M,X = map(int,input().split())
cost_performances = []
for i in range(N):
  book = list(map(int,input().split()))
  cost_performances.append(book)
  for j in range(len(cost_performances)-1):
    cost_performances.append([book[k]+cost_performances[j][k] for k in range(M+1)])
candidate = []
for cost_performance in cost_performances:
  judge = [cost_performance[i+1]>=X for i in range(M)]
  if(False in judge):
    continue
  else:
    candidate.append(cost_performance)
if(len(candidate)==0):
  print(-1)
else:
  cost = [candidate[i][0] for i in range(len(candidate))]
  print(min(cost))

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

a,b,c=ml()
cost=[]
for i in range(a):
    cost.append(ll())
ans=1e18    
flag=1
for i in range(1<<a):
    val=[0]*(b+1)
    for j in range(a):
        if(i&(1<<j)):
            for k in range(b+1):
                val[k]+=cost[j][k]    
    f=0
    for j in val[1:]:            
        if(j<c):
            f=1
            break
    if f==0:
        flag=0
        ans=min(val[0],ans)
if(flag):
    print(-1)
else:    
    print(ans)

Submission status: Accepted

Solution code:
import sys 
from collections import deque
import numpy as np
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
def LS(): return list(sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def Main():
    n,m,x = IL()
    table = np.zeros(m,dtype=int)
    c = deque()
    a = deque()
    for _ in range(n):
        tmp = deque(LI())
        c.append(tmp.popleft())
        a.append(tmp)

    ans = -1
    for bit in range(2**n):
        tmp = 0
        buff = np.zeros_like(table)
        for i in range(n):
            if (bit>>i)&1:
                tmp += c[i]
                buff += a[i]
        if np.all(buff>=x):
            if ans==-1 or tmp<ans:
                ans = tmp
    print(ans)
    return

if __name__=='__main__':
    Main()

Submission status: Accepted

Solution code:
import numpy as np

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

min_C = np.inf
conbi = None
m = 2**N

for i in range(m):
  tmp = []
  for _ in range(N):
    tmp.append(i%2)
    i //= 2
  
  sum_array = np.sum(array[np.where(tmp)], axis=0)
  #print(tmp)
  if np.all(sum_array[1:]>=X):
    if sum_array[0] < min_C:
      min_C = sum_array[0]
      conbi = tmp
      
if conbi is None:
  print(-1)
else:
  print(min_C)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(n)]
p = 12*(10**5)+1
for i in range(2**n):
    di= [0]*(m+1)
    for j in range(n):
        if (i>>j)&1:
            for k in range(m+1):
                di[k] += ls[j][k]
    for l in range(1,m+1):
        if di[l] < x:
            break
    else:
        if p > di[0]:
            p = di[0]
if p <= 12*(10**5):
    print(p)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools

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

ans = []

for s in itertools.product(range(2), repeat=N):

    li = [0 for _ in range(M)]
    cum = 0
    for i, v in enumerate(s):
        if v == 1:
            ca = CA[i]
            cum += ca[0]

            for j, x in enumerate(ca[1:]):
                li[j] += x

        q = [p >= X for p in li]
        if all(q):
            ans.append(cum)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 15 11:10:31 2020

@author: asaka
"""

N, M, X = map(int, input().split())
C = []
A = []
ans = float("inf")

for n in range(N):
    temp = list(map(int, input().split()))
    C.append(temp[0])
    A.append(temp[1:])
    
for i in range(2**N):
    mny = 0
    score = [0]*M
    for j in range(N):
        if i&(2**j)>0:
            mny += C[j]
            for k in range(M):
                score[k] += A[j][k]
    if min(score)>=X:
        ans = min(ans, mny)

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 x in range(n)]
total = [0]*(m+1)
flg = False
mflg = True
min_num = 100100100100100
for i in range(1,2**n):
    for j in range(n):
        if ((i >> j) & 1):
            total = [x + y for (x, y) in zip(a[j], total)]
    for k in range(m):
        if total[1+k] < x:
            mflg = False
            break
    if mflg and total[0] < min_num:
        min_num = total[0]
        flg = True
    total = [0]*(m+1)
    mflg = True
if flg:
    print(min_num)
else:
    print('-1')

Submission status: Accepted

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

for _ in range(N):
    c,*a = map(int,input().split())
    li.append(np.array(a))
    C.append(c)

counter = []

for i in range(1<<N):
    skill_li = np.zeros(M).astype(int)
    sum_price = 0
    for k in range(N):
        if (i>>k) & 1:
            skill_li += li[k]
            sum_price += C[k]
    if all(skill_li>=X):
        counter.append(sum_price)

if len(counter)==0:
    print(-1)
else:
    print(min(counter))

Submission status: Accepted

Solution code:
# C

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

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

ans = -1

# 全部の組み合わせをおこなう
for i in range(2**N):
  skill = [0] * M
  money = 0
  for j in range(N):  # このループが一番のポイント
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      # フラグが立っていたら選ぶ
      money += temp[j][0]
      for k in range(M):
        skill[k] += temp[j][k+1]
  
  if min(skill) >= X:
    if ans == -1:
      ans = money
    else:
      ans= min(money,ans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n, m, x = map(int, input().split())
c = []
a = []
p = [0] * m
for i in range(n):
  l = list(map(int, input().split()))
  c.append(l[0])
  a.append(l[1:])
  for j in range(m):
    p[j] += l[j + 1]

if min(p) < x:
  ans = -1
else:
  l = [0, 1]
  buy = list(itertools.product(l, repeat=n))
  point = []
  price = []
  for  i in range(len(buy)):
    result = [0] * m
    k = 0
    for j in range(n):
      result += np.array(a[j]) * buy[i][j]
      k += c[j] * buy[i][j]
    if min(result) >= x:
      point.append(result)
      price.append(k)
  ans = min(price)
print(ans)

Submission status: Accepted

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

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

ans = 10 ** 10

for i in range(2**N):
    tmp = [0]*M
    tmp2 = 0
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                tmp[k] += l[j][k+1]
            tmp2 += l[j][0]
    flag = True
    for k in range(M):
        if tmp[k] < X:
            flag = False
    if flag:
        ans = min(ans, tmp2)
if ans != 10**10:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
C=[0 for i in range(N)]
A=[[] for i in range(N)]
min_cost=10000000000
for i in range(N):
    C[i],*A[i]=map(int,input().split())
for i in range(1<<N):
    L=[0 for i in range(M)]
    cost=0
    for j in range(N):
        if 1&(i>>j):
            for k in range(M):
                L[k]+=A[j][k]
            cost+=C[j]
    if min(L)>=X:
      min_cost=min(min_cost,cost)
if min_cost==10000000000:
  print(-1)
else:
  print(min_cost)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0] * N
A = [[0] * M] * N
price_min = float('inf')

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

for i in range(2 ** N):
    is_read = [True] * N
    price = 0
    skill = [0] * M

    for j in range(N):
        if((i >> j) & 1):
            is_read[j] = False

    for k in range(N):
        if is_read[k] == True:
            price += C[k]

            for l in range(M):
                skill[l] += A[k][l]

    if min(skill) >= X:
        price_min = min(price_min, price)

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

Submission status: Accepted

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

ans = 1001001001
for s in range(2 ** n):
    C = [0] * m
    cost = 0
    for i in range(n):
        if (s >> i) & 1:
            cost += A[i][0]
            for j in range(m):
                C[j] += A[i][j+1]
        ok = True
        for c in C:
            if c < x:
                ok = False
                break
        if ok:
            ans = min(ans, cost)
 
if ans == 1001001001:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
A=[]
for _ in range(n):
  A.append(list(map(int,input().split()))) 
yeen=[]  
for i in range(2**n):
  rikai=[0]*m
  yen=0
  for j in range(n):
    if ((i>>j)&1):
      yen+=A[j][0]
      for w in range(1,m+1):
        rikai[w-1]+=A[j][w]
    if min(rikai)>=x:
      yeen.append(yen)
if yeen==[]:
  print(-1)
else:
  print(min(yeen))

Submission status: Accepted

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

cost = 1200001
for i in range(2**N):
    skill = [0]*M
    cost_ = 0
    for j in range(N):
        if i>>j & 1:
            cost_+=CA[j][0] #金額
            for k in range(M):
                skill[k] += CA[j][k+1]
    if all([l>=X for l in skill]):
        cost = min(cost_, cost)

if cost == 1200001:
    print(-1)
else:
    print(cost)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C - Skill Up
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""

N, M, X = 0, 0, 0
BOOKS = []


def calc_price(book_combinations, current_answer):
    price = 0
    # calculate understandings
    understandings = [0] * M
    for i in range(len(book_combinations)):
        if book_combinations[i]:
            price += BOOKS[i][0]
            if current_answer < price:
                return -1  # overpriced
            for j in range(len(BOOKS[i][1:])):
                understandings[j] += BOOKS[i][j + 1]
    for u in understandings:
        if u < X:  # couldn't understand
            return -1
    return price


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

    ans = float('inf')
    for i in range(1, 2 ** N):  # => 1: at least one book should be buy
        price = calc_price([(i >> j) & 1 for j in range(N)], ans)
        if 0 < price and price < ans:
            ans = price
    if ans == float('inf'):
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C - Skill Up
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""

N, M, X = 0, 0, 0
BOOKS = []


def calc_price(book_combinations):
    price = 0
    understandings = [0] * M
    for i in range(len(book_combinations)):
        if book_combinations[i]:
            price += BOOKS[i][0]
            for j in range(len(BOOKS[i][1:])):
                understandings[j] += BOOKS[i][j + 1]
    for u in understandings:
        if u < X:  # couldn't understand
            return -1
    return price


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

    ans = float('inf')
    for i in range(1, 2 ** N):  # => 1: at least one book should be buy
        price = calc_price([(i >> j) & 1 for j in range(N)])
        if 0 < price and price < ans:
            ans = price
    if ans == float('inf'):
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
  L=list(map(int,input().split()))
  C.append(L[0])
  A.append(L[1:])
ans=-1
for i in range(1<<N):
  cost=0
  tmp=[0]*M  
  for j in range(N):
    if (i>>j)&1==0:
      continue
    cost+=C[j]
    l=0
    for k in A[j]:
      tmp[l]+=k
      l+=1
    if min(tmp)>=X:
      if ans==-1:
        ans=cost
      else:
        ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
  L=list(map(int,input().split()))
  C.append(L[0])
  A.append(L[1:])
ans=-1
for i in range(1<<N):
  cost=0
  tmp=[0]*M
  for j in range(N):
    if (i>>j)&1==0:
      continue
    cost+=C[j]
    for k in range(M):
      tmp[k]+=A[j][k]
    if min(tmp)>=X:
      if ans==-1:
        ans=cost
      else:
        ans=min(ans,cost)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c,a = [],[]
ans = float('inf')
for i in range(n):
    y = list(map(int,input().split()))
    c.append(y.pop(0))
    a.append(y)
for i in range(2**n):
    b = [0]*m
    cost = 0
    for j in range(n):
        if i&(1<<j):
            cost+=c[j]
            for k in range(m):
                b[k]+=a[j][k]
    for j in range(m):
        if b[j]<x:
            break
    else:
        ans = min(ans,cost)
if ans==float('inf'): print("-1")
else: print(ans)

Submission status: Accepted

Solution code:
import sys
n, m, x = [int(i) for i in sys.stdin.readline().split()]
c_ls = []
a_ls = []
INF = 10**18
for i in range(1,1+n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    c = inp[0]
    a_s = inp[1:]
    c_ls.append(c)
    a_ls.append(a_s)

best = INF
for i in range(1 << n):
    _sum = 0
    scores = [0] * n
    combi = bin(i)[2:].zfill(n)
    for i, c in enumerate(combi):
        if c == "1":
            _sum += c_ls[i]
            scores = [s + a for s, a in zip(scores, a_ls[i])]
    if min(scores) < x:
        continue
    if best > _sum:
        best = _sum
if best == INF:
    print(-1)
else:
    print(best)

Submission status: Accepted

Solution code:
#inport
import sys
import numpy as np
from collections import deque


#input
N,M,X = [int(x) for x in sys.stdin.readline().split()]

g = np.zeros([N,M+1])
for _ in range(N):
    g[_] = [int(x) for x in sys.stdin.readline().split()]

g_split = np.split(g, [1], 1)

money = -1

#bit全数検査
for i in range(2**N):
    #ケースループ毎の初期化
    money_tmp = 0 #お金
    skill_tmp = np.zeros(M) #スキル
    for j in range(N):
        if(( i >> j ) & 1):
            #bitが立っているときの処理
            money_tmp = money_tmp + g_split[0][j]
            skill_tmp = skill_tmp + g_split[1][j]
    #ケース積算終了後の処理
    #スキルが条件を満たしているかの判定
    if np.all(skill_tmp >= X):
        if money == -1:
            money = int(money_tmp[0])
        elif money > money_tmp:
            money = int(money_tmp[0])

print(money)

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:])
res=-1
for i in range(1<<N):
  und=[0]*M
  cost=0
  for j in range(N):
    if (i>>j)&1==0:
      continue
    cost+=C[j]
    for k in range(M):
      und[k]+=A[j][k]
    if min(und)>=X:
      if res==-1:
        res=cost
      else:
        res=min(res,cost)
print(res)

Submission status: Accepted

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

A = []
C = []
ans = float("Inf")

for c , *a in book:
    C.append(c)
    A.append(a)

for bit in range(1<<n):
    algo = [0]*m
    cost = 0
    for i in range(n):
        if bit & (1<<i):
            cost += C[i]
            for idx , a in enumerate(A[i]):
                algo[idx] += a
    if all([True if a >= x else False for a in algo]):
        ans = min(ans , cost)

print(ans if ans != float("Inf") else -1)

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

result = -1
for i in range(1 << N):
    t = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Submission status: Accepted

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

INF = float('inf')
ans = INF

for i in range(2 ** n):
    bag = []
    score = [0] * m
    flg = True
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(j)

    for j in range(1, m + 1):
        for k in bag:
            inc = a[k][j]
            score[j - 1] += inc

    for k in score:
        if k < x:
            flg = False

    if flg:
        pri = 0
        for j in bag:
            pri += a[j][0]
        if pri < ans:
            ans = pri

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
CA = []
ans = 12*(10**5)+1
for n in range(N):
    CA.append(list(map(int,input().split())))

for bit in range(2**N):
    power = [0]*(M+1)
    for n in range(N):
        if bit>>n & 1:
            for i in range(M+1):
                power[i] += CA[n][i]
    rikai = True
    for m in range(M):
        if power[m+1]<X:
            rikai = False
    if rikai:
        ans=min(ans,power[0])
if ans == 12*(10**5)+1:
    ans = -1
print(ans)

Submission status: Accepted

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

min_price = float('inf')
for combo in range(0, 2**N):
    combo = list(map(int, bin(combo)[2:]))
    combo = [0] * (N - len(combo)) + combo
    curr_sums = [0] * M
    curr_price = 0
    for i, val in enumerate(combo):
        if val == 1:
            curr_price += books[i][0]
            for j in range(M):
                curr_sums[j] += books[i][j + 1]
    
    good = True
    for val in curr_sums:
        if val < X:
            good = False
    
    if good:
        min_price = min(min_price, curr_price)

print("{}".format('-1' if min_price >= float('inf') else min_price))

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][0])
    del a[i][0]

INF = 100000000

ans = INF

for i in range(1 << n):
    cost = 0
    d = [0] * m
    for j in range(n):
        if i >> j & 1:
            cost += c[j]
            for k in range(m):
                d[k] += a[j][k]
    ok = True
    for j in range(m):
        if d[j] < x:
            ok = False
    if ok:
        ans = min(ans, cost)
if ans == INF:
    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)]

min_value = -1
for i in range(2**N):
    sum = [0 for k in range(M+1)]
    for j in range(N):
        if (i >> j) & 1:
            sum = [x+y for x, y in zip(sum, book[j])]
    if min(sum[1:]) >= X and (min_value > sum[0] or min_value == -1):
        min_value = sum[0]

print(min_value)

Submission status: Accepted

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

def main():
    N, M, X = map(int, input().split())
    a = np.array([list(map(int, input().split())) for i in range(N)], dtype=int)

    ans = int(1e15)
    for i in range(2**N):
        tmp = np.zeros(M+1, dtype=int)
        for j in range(N):
            if i&1:
                tmp += a[j]
            i >>= 1
        if np.all(tmp[1:] >= X):
            ans = min(ans, tmp[0])
    
    if ans > int(1e9):
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, x = list(map(int, input().split()))
lists = []
result_price = 0
existed = False

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

for i in range(1 << n):
  flag = True
  scores = [0] * m
  tmp_price = 0
  for j in range(n):
    if i & (1 << j):
      for k in range(m):
        scores[k] += lists[j][k+1]
      tmp_price += lists[j][0]
  for l in range(m):
    if scores[l] < x:
      flag = False
      break
  if flag and (result_price > tmp_price or result_price == 0):
    existed = True
    result_price = tmp_price
if existed:
  print(result_price)
else:
  print(-1)

Submission status: Accepted

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

l=[]
suml=[]
for  i in range(2**n):
  bag=[0]*n
  #print("pattern {}: ".format(i), end="")
  for j in range(n):
    if((i >> j) & 1):
      bag[j]=1
      
  l.append(bag)
  
for bag in l:
  ll=[0]*m
  s=0
  for b in range(len(bag)):
    if bag[b] == 0:
      continue
    #print("bag: ", bag, b)
    #print("sum:", s)
    s+=a[b][0]
    for im in range(1, m+1):
      #print("im", im)
      ll[im-1] += a[b][im]
      #print(ll)
    if len([i for i in ll if i >= x]) == m:
      suml.append(s)
      #print("money: ", s)

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

Submission status: Accepted

Solution code:
n, m, x =map(int,input().split())
s = [list(map(int, input().split())) for _ in range(n)]
ans = 10000000
for i in range(2 ** n):
  bag = [0]*(m+1)
  for j in range(n):
    if ((i>>j)&1):
        for _ in range(m+1):
          bag[_] += s[j][_]
  ##print(bag)
  if (min(bag[1:]) >= x and ans > bag[0]):
    ans = bag[0]
    
if ans == 10000000:
  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)]

yen_min = float('inf')
for bit in range(2 ** n):
    array = []
    for i in range(n):
        if bit>>i & 1:
            array.append(i)
    check = [0]*(m+1)
    for i in array:
        for j in range(m+1):
            check[j] += ca[i][j]
    flag = True
    for i in range(1,m+1):
        if check[i] < x:
            flag = False
    if flag:
        yen_min = min(yen_min, check[0])
if yen_min == float('inf'):
    print(-1)
else:
    print(yen_min)

Submission status: Accepted

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

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

ans = 10**9
for i in range(1, N+1):
    for j in combinations(Books, i):
        understand = [0] * M
        cost = 0
        for book in j:
            cost += book[0]
            for p in range(M):
                understand[p] += book[p+1]
        if all(understand[p] >= X for p in range(M)):
            ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import sys
n,m,x=map(int,input().split())
A=[]
for i in range(n):
    ca=list(map(int,input().split()))
    A.append(ca)
ans=10**7

for i in range(2**n):#n冊をそれぞれ選ぶか選ばないか
    tmp=[0]*m
    cost=0
    for j in range(n):#ある選び方
        if (1<<j)&i:
            cost+=A[j][0]
            for k in range(m):
                tmp[k]+=A[j][k+1]
    check=True
    for l in range(m):#理解度がx以上か判定
        if tmp[l]<x:
            check=False
            break
    #else:
    if check:
        ans=min(ans,cost)#すべてのアルゴリズムの目標理解度を満たすとき
                        #(for文が最後まで実行されるとelseが実行)
if ans==10**7:#ansが更新されない場合
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
import sys
n,m,x=map(int,input().split())
A=[]
for i in range(n):
    ca=list(map(int,input().split()))
    A.append(ca)
ans=10**7

for i in range(2**n):#n冊をそれぞれ選ぶか選ばないか
    tmp=[0]*m
    cost=0
    for j in range(n):#ある選び方
        if (1<<j)&i:
            cost+=A[j][0]
            for k in range(m):
                tmp[k]+=A[j][k+1]
    for l in range(m):#理解度がx以上か判定
        if tmp[l]<x:
            break
    else:
        ans=min(ans,cost)#すべてのアルゴリズムの目標理解度を満たすとき
if ans==10**7:#ansが更新されない場合(for文が最後まで実行されるとelseが実行)
    ans=-1
print(ans)

Submission status: Accepted

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

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

#print(clist)

total_all=[]
for i in range(2**N):
    total=np.zeros(M+1)
    for j in range(N):
        
        # iを2進数表記した場合の下から数えてj番目が1ならtrue
        if ((i >> j) & 1):
            total=total+np.array(clist[j])
    total_all.append(list(total))

#print(total_all)
ans=[]
#print(total_all[1][1:M+1])

for i in range(len(total_all)):
    if min(total_all[i][1:M+1])>=X:
        ans.append(total_all[i][0])

if len(ans)>=1:
    print(int(min(ans)))
else:
    print("-1")

Submission status: Accepted

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

ans = 10**9
for i in range(1,n+1):
  for j in combinations(ca, i):
    t = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        t[l] += k[l]
    
    if all(t[a] >= x for a in range(1,m+1)):
      ans = min(ans, t[0])
      
if ans == 10**9:
  print(-1)
else:
  print(ans)