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:
# TODO: itertools を使わない解き方
# https://python.civic-apps.com/itertools-combinations/

import sys
# sys.stdin = open('input.txt')

import itertools

def add_lists(a, b):
    result = [0 for i in range(len(a))]
    for i in range(len(a)):
        result[i] = a[i] + b[i]
    return result

n, m, x = map(int, input().split())
c = []
a = [[0] for i in range(n)]
for i in range(n):
    cj, *aj = input().split()
    c.append(int(cj))
    aj = list(map(int, aj))
    a[i] = aj

# solution 1 (itertools)
# INF = float('inf')
# ans = INF
#
# for flags in itertools.product([0,1], repeat=n):
#     tot = [0 for i in range(m)]
#     now = 0
#     for i in range(len(flags)):
#         if flags[i] == 1:
#             tot = add_lists(tot, a[i])
#             now += c[i]
#     flag = True
#     for i in tot:
#         if i < x:
#             flag = False
#     if flag:
#         ans = min(ans, now)
#
# if ans == INF:
#     print(-1)
# else:
#     print(ans)

# solution 2
INF = float('inf')
ans = INF

for s in range(1<<n):  # ビット演算ですべての組み合わせを試す
    tot = [0 for i in range(m)]  # 理解度
    now = 0  # 現在のコスト
    for i in range(n):
        if s >> i & 1:  # 右シフトすると対象になるかどうかのフラグが一番右の位に来る -> 1 とビットマスク
            tot = add_lists(tot, a[i])
            now += c[i]
    flag = True
    for i in tot:
        if i < x:
            flag = False
    if flag:
        ans = min(ans, now)

if ans == 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 = 10**9+7

for bit in range(2**N):
    rikai = [0]*M
    money = 0
    for i in range(N):
        if (bit >> i) & 1 == 1:
            for j in range(M):
                rikai[j] += A[i][j]
            money += C[i]
    if min(rikai) >= X:
        ans = min(ans,money)
        
if ans == 10**9+7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for i in range(n)]
INF = 10**12

ans = INF
l = [0, 1]
for v in product(l, repeat=n):
    rikai = [0 for _ in range(m)]
    cost = 0
    for i in range(n):
        if v[i]:
            c = ca[i][0]
            a = ca[i][1:]
            cost += c
            for j in range(m):
                rikai[j] += a[j]
    f = True
    for i in range(m):
        if rikai[i] < x:
            f = False
    if f:
        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 = [list(map(int,input().split())) for _ in range(n)]

min_cost = float('inf')
 
for i in range(2**len(book_list)):  # 空集合を除く場合はrange(1, 2**len(list1))
    # list2 = []
    cost = 0
    score_list = [0 for _ in range(m)]
    for j in range(len(book_list)):
        if (i >> j) &1 == 1:
            cost += book_list[j][0]
            for idx in range(m):
                score_list[idx] += book_list[j][idx+1]
    if min(score_list) >= x:
        min_cost = min(min_cost,cost)

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

import numpy as np
from itertools import product

n, m, x = map(int, readline().split())
ca = np.array(read().split(), np.int64).reshape((n, m + 1))
INF = 10 ** 9

c = ca[:, 0]
a = ca[:, 1:]

p = np.array([e for e in product([1, 0], repeat=n)], np.int64)
rikai = np.dot(p, a)
cost = np.dot(p, c)
idx = rikai.min(axis=1) >= x
if idx.any():
    ans = cost[idx].min()
else:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca_list = []
for i in range(n):
    ca_list.append(list(map(int, input().split())))
ans = 10**10
    
for i in range(2**n):
    suml = [0]*m
    money = 0
    for j in range(n):
        if i>>j&1:
            for k in range(1, m+1):
                suml[k-1] += ca_list[j][k]
            money += ca_list[j][0]
    ok = 1
    for a in range(m):
        if suml[a] < x:
            ok =0
            break
    if ok:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

import numpy as np
from itertools import product

n, m, x = map(int, readline().split())
ca = np.array(read().split(), np.int64).reshape((n, m + 1))
INF = 10 ** 9

c = ca[:, 0]
a = ca[:, 1:].T

ans = INF
for p_li in product([1, 0], repeat=n):
    p = np.array(p_li)
    rikai = a * p
    sm = rikai.sum(axis=1)
    if sm.min() >= x:
        cost = (c * p).sum()
        ans = min(ans, cost)

if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

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

ans = float('inf')
flg = False
for i in range(1<<n):
    und = [0 for _ in range(m)]
    price = 0
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                und[k] += cl[j][k+1]
            price += cl[j][0]
    und = [1 if i >= x else 0 for i in und]
                
    if all(und):
        flg = True
        ans = min(ans,price)
        
print(ans if flg else '-1')

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import product
def main():
    n,m,x=map(int,input().split())
    CA=[[int(_) for _ in input().split()] for i in range(n)]
    ans=10**10
    n_lis=list(product([True,False],repeat=n))
    for comb in n_lis:
        cunt=0
        A=[0]*m
        for i,ca in enumerate(CA):
            if comb[i]:
                cunt+=ca[0]
                for j,aa in enumerate(ca[1:]):
                    A[j]+=aa
        for a in A:
            if a<x:
                break
        else:
            ans=min(ans,cunt)
    if ans==10**10:
        print(-1)
    else:
        print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

costmin=float('inf')
for k in range(2**N):
  tansaku=k
  koubai=[0 for i in range(N)]
  rikaido=[0 for i in range(M)]
  cost=0
  for i in range(N-1):
    koubai[i]=tansaku//(2**(N-i-1))
    tansaku=tansaku%(2**(N-i-1))
  koubai[-1]=tansaku
  for i in range(N):
    if koubai[i]==1:
      cost+=C[i]
      for j in range(M):
        rikaido[j]+=A[i][j]
  for i in range(M):
    if rikaido[i]<X:
      break
  else:
    costmin=min(costmin,cost)
if costmin!=float('inf'):
  print(costmin)
else:
  print(-1)

Submission status: Accepted

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

a = []
for i in range(n):
    b = list(map(int, input().split()))
    a.append(b)


def calcPoint(point, n):
    for i in range(m):
        point[i] += a[n][i+1]
    return point


def judgePoint(point):
    for i in range(m):
        if point[i] < x:
            return False
    return True


ans = []
for i in range(2**n):  # patarn数
    buy = []
    for j in range(n):  # n bit
        if((i >> j) & 1):  # iをj bit 右にずらして1ならば
            buy.append(1)
        else:
            buy.append(0)
    price = 0
    point = [0]*m
    for i in range(n):
        if buy[i] == 1:
            calcPoint(point, i)
            price += a[i][0]
    if judgePoint(point):
        ans.append(price)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
import numpy as np



def main():
    N, M, X = map(int, input().split())
    C = []
    A = []
    INF = 10 ** 10
    ans = INF
    for i in range(N):
        lists = [int(c) for c in input().split()]
        ci = lists[0]
        ai = lists[1:]
        C.append(ci)
        A.append(ai)


    for i in range(1 << N):
        ability = np.zeros((M, ))
        cost = 0
        for j in range(N):
            if (i >> j) & 1:
                ability += np.array(A[j])
                cost += C[j]
        if sum(ability >= X) == M:
            ans = min(ans, cost)

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

    
    



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np

_,*_t=[list(map(int,i.split())) for i in open(0)]
n=_[0]
m=_[1]
x=_[2]
table=np.array(_t)
patterns=list(itertools.product([False,True], repeat=n))
value=9000000


def boolAchieve(nums):
  for i in range(1,m+1):
    if nums[i]<x:
      return False
  return True


tmp=np.sum(table,axis=0)
if not boolAchieve(tmp):
  print(-1)
  exit()


for i in range(1,2 ** n):
  selects=patterns[i]
  picks=np.sum(table[selects,:],axis=0)
  if not boolAchieve(picks):
    continue
  value=min(value,picks[0])

  
print(value)

Submission status: Accepted

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

ans = 10 ** 18
for i in range(2 ** N):
    cost = 0
    each_alg = [0 for _ in range(M)]
    for j in range(N):
        if (i >> j) & 1:
            cost += CA[j][0]
            for k in range(M):
                each_alg[k] += CA[j][k+1]
    if min(each_alg) >= X:
        ans = min(ans, cost)

if ans == 10**18:
    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(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Submission status: Accepted

Solution code:
from itertools import product

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 p in product([True, False], repeat = N):
    t = [0] * M
    c = 0
    for j in range(N):
        if not p[j]:
            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:
import numpy as np

_,*_t=[list(map(int,i.split())) for i in open(0)]
n=_[0]
m=_[1]
x=_[2]
table=np.array(_t)
value=9000000


def boolAchieve(nums):
  for i in range(1,m+1):
    if nums[i]<x:
      return False
  return True


tmp=np.sum(table,axis=0)
if not boolAchieve(tmp):
  print(-1)
  exit()


for i in range(1,2 ** n):
  #numpyで書いてみた
  slist=np.right_shift(i,np.arange(n))
  blist=np.bitwise_and(slist,1).tolist()
  selects=list(map(bool,blist))
  #元のコード
  #selects=[bool((i >> j) & 1) for j in range(n)]

  picks=np.sum(table[selects,:],axis=0)
  if not boolAchieve(picks):
    continue
  value=min(value,picks[0])

  
print(value)

Submission status: Accepted

Solution code:
import numpy as np

_,*_t=[list(map(int,i.split())) for i in open(0)]
n=_[0]
m=_[1]
x=_[2]
table=np.array(_t)
value=9000000


def boolAchieve(nums):
  for i in range(1,m+1):
    if nums[i]<x:
      return False
  return True


tmp=np.sum(table,axis=0)
if not boolAchieve(tmp):
  print(-1)
  exit()


for i in range(1,2 ** n):
  slist=np.right_shift(i,np.arange(n))
  blist=np.bitwise_and(slist,1).tolist()
  selects=list(map(bool,blist))
  #  selects=[bool((i >> j) & 1) for j in range(n)]
  picks=np.sum(table[selects,:],axis=0)
  if not boolAchieve(picks):
    continue
  value=min(value,picks[0])

  
print(value)

Submission status: Accepted

Solution code:
from itertools import product
n,m,x=map(int,input().split())
c=[0]*n
a=[0]*n
INF=10**9
for i in range(n):
  d,*b=map(int,input().split())
  c[i]=d
  a[i]=b
ans=INF
for z in product([0,1],repeat=n):
  u=[0]*m
  cost=0
  for i in range(n):
    cost+=c[i]*z[i]
    for j in range(m):
      u[j]+=a[i][j]*z[i]
  flg=True
  for j in range(m):
    if u[j]<x:
      flg=False
  if flg:
    ans=min(ans,cost)
if ans==INF:
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
n, m, x = [int(e) for e in input().split()]

import numpy as np
import itertools

all = np.zeros(n*(m+1)).reshape(n,m+1)

for i in range(n):
    all[i] += [int(e) for e in input().split()]

b = itertools.product([True,False],repeat=n)

dp=10**10

for i in b:
    i = np.array(i)
    if (all[i][:,1:].sum(axis = 0) >=x).all() :
        dp = min(dp,all[i][:,0].sum(axis = 0))

if dp ==10**10:
    dp = -1
print(int(dp))

Submission status: Accepted

Solution code:
n, m, x = [int(e) for e in input().split()]

import numpy as np

all = np.zeros(n*(m+1)).reshape(n,m+1)

for i in range(n):
    all[i] += [int(e) for e in input().split()]

bool_list = np.array([])
a = []
b = []
def make(n):
    if len(a) == n:
        b.append([0 for _ in range(n)])
        for i,v in enumerate(a) :
            if v == True:
                b[-1][i] = True
            else:
                b[-1][i] = False
    else:
        for i in [True,False]:
            a.append(i)
            make(n)
            a.pop()

make(n)
c=np.array(b)

dp=10**10

for i in c:
    if (all[i][:,1:].sum(axis = 0) >=x).all() :
        dp = min(dp,all[i][:,0].sum(axis = 0))

if dp ==10**10:
    dp = -1
print(int(dp))

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
def LI(): return list(MI())
if __name__ == "__main__":
    N, M, X = MI()
    C = [LI() for _ in range(N)]
    ans = float('inf')
    for i in range(1<<N):
        score = [0] * M
        money = 0
        for j in range(N):
            if (1<<j) & i != 0:
                money += C[j][0]
                for k in range(M):
                    score[k] += C[j][k+1]
        if min(score) >= X:
            ans = min(ans, money)
    print(ans if ans != float('inf') else -1)

Submission status: Accepted

Solution code:
# 3 3 10
# 60 2 2 4
# 70 8 7 9
# 50 2 3 9

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

# 120

# 180 12 12 22 OK
# 130 10 9 13 NO
# 120 10 10 18 OK
# 110 4 5 13 NO
# 70 8 7 9 NO
# 60 2 2 4 NO
# 50 2 3 9 NO
# 0 0 0 0 NO

from itertools import combinations
from operator import itemgetter

def get_min_price(N, M, X, C_i, A_i):
    combs = []
    min_price = 0

    for i in range(N+1):
        for comb in combinations(list(range(N)), i):
            price = sum([C_i[j] for j in comb])
            combs.append((price, comb))
    # print('N:', N)
    # print('combs:', combs)

    for price, comb in sorted(combs, key=itemgetter(0)):
        scores = [0] * M
        # print('comb:', comb)
        for j in comb:
            for k in range(M):
                scores[k] += A_i[j][k]
            
            if all(list(map(lambda score: score >= X, scores))):
                return price

            # print('scores:', scores)

    return -1


if __name__ == '__main__':
    N, M, X = map(int, input().split())
    C_i, A_i = [], []
    for i in range(N):
        temp = list(map(int, input().split()))
        # print(temp)
        C_i.append(temp[0])
        A_i.append(temp[1:])
    res = get_min_price(N, M, X, C_i, A_i)
    print(res)

Submission status: Accepted

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

c = []
d = []
for i in range(n):
	s = list(map(int, input().split()))
	d.append(s)
ans = 10**9
for i in range(1,n+1):
	for j in itertools.combinations(d,i):
		s = [0 for ii in range(m+1)]
		for k in j:
			for l in range(m+1):
				s[l] += k[l]
		y = min(s[1:])
		if y >= x:
			ans = min(ans,s[0])
if ans == 10**9:
	print (-1)
else:
	print (ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
book=[list(i for i in map(int,input().split()))for _ in range(n)]
t=[0]
def dfs(seq, seq2, c):
  judgeSeq(calSkills(seq), c) # 条件を満たすか判定
  if len(seq2)==0: return # 終端条件: n冊目の本を購入したら打ち切り
  for i in range(len(seq2)):
    seq.append(seq2[i])
    dfs(seq, seq2[i+1:], c)
    seq.pop()

def calSkills(seq):
  res = [0]*(m+1)
  for i in seq:
    for j in range(m+1):
      res[j] += book[i][j]
  return res

def judgeSeq(skills, c):
  if all(x<=i for i in skills[1:]):
    t[0]+=1
    c[0] = min(c[0], skills[0])

if __name__ == "__main__":
  c = [sum(book[i][0] for i in range(n))]
  dfs([], [i for i in range(n)], c)
  print(c[0] if t[0]>0 else -1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

_,*_t=[list(map(int,i.split())) for i in open(0)]
n=_[0]
m=_[1]
x=_[2]
table=np.array(_t)
value=9000000


def boolAchieve(nums):
  for i in range(1,m+1):
    if nums[i]<x:
      return False
  return True


tmp=np.sum(table,axis=0)
if not boolAchieve(tmp):
  print(-1)
  exit()


for i in range(1,2 ** n):
  selects=[bool((i >> j) & 1) for j in range(n)]
  picks=np.sum(table[selects,:],axis=0)
  if not boolAchieve(picks):
    continue
  value=min(value,picks[0])

  
print(value)

Submission status: Accepted

Solution code:
def C():
    N, M, X = map(int, input().split())
    C = []
    A = []
    for i in range(N):
        temp = [int(n) for n in input().split()]
        C.append(temp[0])
        A.append(temp[1:])
    
    ans = [float('inf')]
    def helper(i, skills, cost):
        if i == N:
            for s in skills:
                if s < X:
                    return
            ans[0] = min(ans[0], cost)
            return
        helper(i+1, [skills[j]+A[i][j] for j in range(M)], cost+C[i])
        helper(i+1, skills, cost)

    for i in range(N):
        helper(i, [0]*M, 0)
    
    if ans == [float('inf')]:
        print(-1)
        return
    print(ans[0])
C()

Submission status: Accepted

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

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

ans = 10**12
for i in range(1<<n):
    rikai  = [0] * m
    cost = 0
    for j in range(n):
        if i&(1<<j):
            # 本を購入
            cost += C[j]
            for k in range(m):
                rikai[k] += A[j][k]            
    a = sum([1 for r in rikai if r >= x])
    if a == m:
        ans = min(ans,cost)
print(ans if ans != 10**12 else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
INF = float("inf")
import sys,collections

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

C = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param

ALL = [0]*(M+1)
for a in C:
    for i in range(M+1):
        ALL[i] += a[i]
#print(ALL,X)
if any(e < X for e in ALL[1:]):
    print(-1)
    exit()

m = INF
def backtrack(n,c):
    #print(n,c)
    if n == N:
        if all(a >= X for a in c[1:]):
            #print("OK",n,c,X)
            global m
            m = min(m,c[0])
        return
    backtrack(n+1,c)#not select
    backtrack(n+1,[a+b for a,b in zip(c,C[n])])#select

backtrack(0,[0]*(M+1))
print(m)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = []
c = 2000000
for i in range(n):
    a.append(list(map(int, input().split())))
for i in range(2**n):
    b = [0]*(m+1)
    for j in range(n):
        if i%2 == 1:
            for k in range(m+1):
                b[k] += a[j][k]
        i //= 2
    d = 0
    for j in range(m):
        if b[j+1] < x:
            d += 1
    if d == 0:
        c = min(c, b[0])
if c == 2000000:
    c =-1
print(c)

Submission status: Accepted

Solution code:
import itertools

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 = 10**10
for s in itertools.product(range(2), repeat=n):
  cost = 0
  skill = [0] * m
  for i in range(n):
    if s[i] == 0:
      continue
    cost += c[i]
    for j in range(m):
      skill[j] += a[i][j]
  if min(skill) >= x:
    ans = min(ans, cost)
if ans == 10**10:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
c=[]
ma=[0]*m
for i in range(n):
  cc,*aa=map(int,input().split())
  a.append(aa)
  c.append(cc)
  for j in range(m):ma[j]+=aa[j]
if min(ma)<x:exit(print(-1))
ans=sum(c)
for i in range(1,1<<n):
  f=[0]*m
  cc=0
  for j in range(n):
    if i&(1<<j):
      cc+=c[j]
      for k in range(m):
        f[k]+=a[j][k]
  if min(f)>=x:ans=min(ans,cc)
print(ans)

Submission status: Accepted

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

# C - Skill Up
n, m, x = map(int, input().split())
books = []

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

ans = sys.maxsize

for i in range(1, pow(2, n)):
	s = format(i, 'b')
	bin_str = s.zfill(n)
	
	skills = [0] * m
	price = 0
	
	for j in range(n):
		if bin_str[j] == '1':
			price += books[j][0]
			
			for k in range(1, m + 1):
				skills[k-1] += books[j][k]			
				
	if min(skills) >= x:
		ans = min(ans, price)

if ans == sys.maxsize:
	print(-1)
else:
	print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

saisyo = float("inf")
for i in itertools.product(range(2), repeat=N):
    a = [0]*M
    gokei = 0
    for j in range(N):
        if i[j] == 1:
            gokei += A[j][0]
            for k in range(1, M+1):
                a[k-1] += A[j][k]
    if min(a) >= X:
        saisyo = min(saisyo, gokei)

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

Submission status: Accepted

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

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

    min_total_cost = 10**9

    for i in range(2**N):
        total_cost = 0
        learned = [0] * M

        for j in range(N):
            if (i >> j) & 1:
                cost, *points = books[j]
                total_cost += cost

                learned = [x + y for x, y in zip(learned, points)]

        if min(learned) >= X:
            min_total_cost = min(min_total_cost, total_cost)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product


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

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

    min_total_cost = 10**9

    for read_flags in product((True, False), repeat=N):
        to_read_books = books[read_flags, :]
        total_cost = to_read_books[:, 0].sum()
        increased_levels = to_read_books[:, 1:].sum(axis=0)

        if min(increased_levels) >= X:
            min_total_cost = min(min_total_cost, total_cost)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# AtCoder Beginner Contest 167
N,M,X=map(int,input().split(" "))
array=[]
_INF_ = 1001001001
ans = _INF_
for i in range(N):
     H = input().rstrip()
     array.append(H.split(" "))
# print(array)

for i in range(1<<N): #2の3条になる(1をNビット右にシフトするから)
    cost = 0
    understand = [0 for un in range(M)]
    # print(understand)
    for j in range(N):
        if(((i>>j)&1)): #a&b : AND:論理積 100*010 = 000, 100+100=100,シフトしたあと１との論理積を取ることで必要なビット田だけ取り出せる
            ar = array[j][0]
            cost+=int(ar)
            for un in range(M):
                a1 = array[j][un+1]
                understand[un]+=int(a1)
        ok = True
    for un in range(M):
        if understand[un]<X:
            ok = False
    if ok:
        ans = min(ans, cost)
        # print(understand)
        # print(cost)
if(ans == _INF_):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
candidates = []

def get_candidate(indices, current, num):
  global candidates

  if len(current) == num:
    candidates.append(current.copy())
    return
  
  for i, v in enumerate(indices):
    current.append(v)
    get_candidate(indices[i+1:], current, num)
    current.pop()
  
n, m, x = list(map(lambda x: int(x), input().split(' ')))
books = []

for i in range(0, n):
  p = list(map(lambda x: int(x), input().split(' ')))
  books.append((p[0], p[1:]))

indices = list(range(0, n))

for i in range(1, n+1):
  get_candidate(indices, [], i)

flag = False
min_price = 1000000000

for c in candidates:
  price = 0
  a = [0] * m
  
  for s in c:
    price += books[s][0]

    for i in range(m):
      a[i] += books[s][1][i]

  for t in a:
    if t < x:
      flag = True
      break

  if flag:
    flag = False
    continue
  
  min_price = min(min_price, price)

if min_price == 1000000000:
  print("-1") 
else:
  print(min_price)

Submission status: Accepted

Solution code:
import math
N , M , X =  map(int,input().split())
A = {}
B = {}
ANS = 100000000000
for i in range(1,N+1):
    A[i]=list(map(int,input().split()))
for i in range(1,2**N):
    l = str(bin(i))
    n = len(l)
    ans=0
    for s in range(1,M+1):
        B[s]=0
    for k in range(1,n+1):
        if l[-k] == "1":
            ans = ans + A[k][0]
            for s in range(1,M+1):
                B[s] += A[k][s]
    if all((B[l] >= X for l in range(1,M+1))):
        ANS = min(ans,ANS)
if ANS == 100000000000:
    print("-1")
else:
    print(ANS)

Submission status: Accepted

Solution code:
import numpy as np

_,*_t=[list(map(int,i.split())) for i in open(0)]
n=_[0]
m=_[1]
x=_[2]
table=np.array(_t)
value=9000000


def boolAchieve(nums):
  for i in range(1,m+1):
    if nums[i]<x:
      return False
  return True

  
def makeBoolList(nums):
  ls=[]
  sNums=str(nums)
  for i in range(len(sNums)):
    if sNums[i]=="0":
      ls.append(False)
    else:
      ls.append(True)
  return ls


tmp=np.sum(table,axis=0)
if not boolAchieve(tmp):
  print(-1)
  exit()


for i in range(1,2 ** n):
  row=format(i,'b').zfill(n)
  selects=makeBoolList(row)
  picks=np.sum(table[selects,:],axis=0)
  if not boolAchieve(picks):
    continue
  value=min(value,picks[0])

  
print(value)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

n,m,x = map(int, input().split())
q = [np.array(list(map(int, input().split()))) for _ in range(n)]
L=[]
for i in range(1,n+1):
    for j in list(combinations(q,i)):
        S = np.sum(j, axis=0)
        if all([k >= x for k in S[1:]]):
            L.append(S[0])

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

Submission status: Accepted

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

final = 1000000000

for i in range(1, 2**N):
    ans = 0
    rikai = [0]*M
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(1, M+1):
                rikai[k-1] += A[j][k]
            ans += A[j][0]
    if all(el >= X for el in rikai):
        final = min(final, ans)

if final == 1000000000:
    print(-1)
else:
    print(final)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(" "))
book_information = []
result = 12 * 10**5 + 1
for i in range(N):
	book_information.append(input())
for i in range(1, 1 << N):
  bought_book = []
  n = 0
  cost = 0
  skill = [0 for j in range(M)]
  for j in range(N):
    if (i >> j) & 1:
      bought_book.append(book_information[j])
      n += 1
  for j in range(n):
    bought_book_information = list(bought_book[j].split(" "))
    cost += int(bought_book_information[0])
    for k in range(M):
      skill[k] += int(bought_book_information[k + 1])
  if all(x >= X for x in skill):
    result = min(result, cost)
if result == 12 * 10**5 + 1:
  print(-1)
else:
  print(result)

Submission status: Accepted

Solution code:
from itertools import product
 
N, M, X = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
ans = float("inf")
for i in product(range(2),repeat=N):
    ans1=0
    l=[0 for i in range(M)]
    for j in range(N):
        if i[j]==1:
            ans1+=A[j][0]
            for k in range(M):
                l[k]+=A[j][k+1]
    if min(l)>=X:
        ans=min(ans,ans1)
if ans==float("inf"):
    print(-1)
else:
    print(ans)