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: Wrong Answer

Solution code:
# abc167_c.py
# https://atcoder.jp/contests/abc167/tasks/abc167_c

# C - Skill Up /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが M個あります。 最初、各アルゴリズムの理解度は 0です。
# 高橋くんが書店に行くと、N冊の参考書が売っていました。
# i 番目の参考書 (1≤i≤N) は Ci 円で売られていて、購入して読むことで、各 j (1≤j≤M) について j 番目のアルゴリズムの理解度が Ai,j上がります。 
# また、それ以外の方法で理解度を上げることはできません。
# 高橋くんの目標は M個すべてのアルゴリズムの理解度を X以上にすることです。
# 高橋くんが目標を達成することが可能か判定し、可能な場合は目標を達成するのに必要な金額の最小値を計算してください。

# 制約
#     入力はすべて整数
#     1≤N,M≤12
#     1≤X≤105
#     1≤Ci≤105
#     0≤Ai,j≤105

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N M X
# C1 A1,1 A1,2 ⋯ A1,M
# C2 A2,1 A2,2 ⋯ A2,M
# ⋮
# CN AN,1 AN,2 ⋯ AN,M

# 出力
# 高橋くんが目標を達成できないならば -1 を、 そうでなければ目標を達成するのに必要な金額の最小値を出力せよ。

# 入力例 1
# 3 3 10
# 60 2 2 4
# 70 8 7 9
# 50 2 3 9

# 出力例 1
# 120

# 2,3番目の参考書を購入すると 120 円ですべてのアルゴリズムの理解度を 10以上にすることができ、これが最小値です。

# 入力例 2
# 3 3 10
# 100 3 1 4
# 100 1 5 9
# 100 2 6 5

# 出力例 2
# -1

# すべての参考書を購入しても 1つ目のアルゴリズムの理解度が 10に達しません。

# 入力例 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

# 出力例 3
# 1067


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    N, M, X = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    valueses = list()
    for i in range(N):
        valueses.append(list(map(int, lines[i+1].split())))

    result = 9999

    for i in range(2**N):
        pattern = format(int(format(i, 'b')), '0=' + str(N))
        # pattern = '11110100'
        cost = 0
        scores = [0] * M
        for n in range(N):
            # log(f'pattern[{n}]=[{pattern[n]}]')
            if pattern[n] == '1':
                cost += valueses[n][0]
                # log(f'cost=[{cost}]')
                for m in range(M):
                    scores[m] += valueses[n][m+1]
        log(f'scores=[{scores}]')
        flag = True
        # log(f'flag=[{flag}]')
        for m in range(M):
            if scores[m] < X:
                # log(f'scores[{m}]=[{scores[m]}]')
                flag = False
        log(f'flag=[{flag}]')
        log(f'min(scores)=[{min(scores)}]')
        if min(scores) >= X:
            log(f'if min(scores) >= X:, result=[{result}], cost=[{cost}], result > cost=[{result > cost}]')
            if result is None:
                result = cost
            elif result > cost:
                log(f'pattern=[{pattern}]')
                result = cost
        log(f'result=[{result}]')
        log(f'cost=[{cost}]')
        # exit()

    if result is None:
        result = -1

    return [result]


# 引数を取得
def get_input_lines():
    line = input()
    N, M, X = list(map(int, line.split()))
    lines = list()
    lines.append(line)
    for _ in range(N):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3 3 10', '60 2 2 4', '70 8 7 9', '50 2 3 9']
        lines_export = [120]
    if pattern == 2:
        lines_input = ['3 3 10', '100 3 1 4', '100 1 5 9', '100 2 6 5']
        lines_export = [-1]
    if pattern == 3:
        lines_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']
        lines_export = [1067]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
ce = list(list(map(int, input().split())) for _ in range(n))
cst = []
for i in range(2**n):
    kn = [0 for _ in range(m)]
    for j in range(n):
        if i >> j & 1:
            kn = [kn[k] + ce[j][k] for k in range(m)]
    if all(kn[i] >= x for i in range(1, m)):
        cst.append(kn[0])
print(min(cst) if cst != [] else -1)

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
ce = list(list(map(int, input().split())) for _ in range(n))
cst = []
for i in range(2**n):
    kn = [0 for _ in range(m)]
    for j in range(n):
        if i >> j & 1:
            kn = [kn[k] + ce[j][k] for k in range(m)]
    if all(kn[i] >= x for i in range(1, m)):
        cst.append(kn[0])
print('-1' if cst == [] else min(cst))

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
ce = list(list(map(int, input().split())) for _ in range(n))
cst = []
for i in range(2**n):
    kn = [0 for _ in range(m)]
    for j in range(n):
        if i >> j & 1:
            kn = [kn[k] + ce[j][k] for k in range(m)]
    if all(kn[i] >= x for i in range(1, m)):
        cst.append(kn[0])
print(-1 if cst == [] else min(cst))

Submission status: Wrong Answer

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

n,m,x=input2()
CA=[]
ans=10**9

for _ in range(n):
	CA.append(input_array())

# ビット全探索
for i in range(2**n):
	bag=[]
	for j in range(n): #ビット全探索
		if (i>>j) & 1:
			bag.append(CA[j])
	enoughs=0 #スキルがx以上身に付く数
	skills=[0]*m #身に付くスキルの合計
	money=0 #探索中の金額

	for b in bag:
		money+=b[0]
		for k in range(1,m+1):
			skills[k-1]+=b[k]
			if skills[k-1]>=x:
				enoughs+=1
	if m==enoughs: #スキルが充足
		if money<ans:
			ans=money #価格の更新
if ans==10**9:
	print(-1)
else:
	print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

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

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

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

full = []
for r in range(n):
  comb = list(itertools.combinations(lis,r))
  full.extend(comb)

for i in full:
  sum_ = np.zeros(m+1)
  
  for k in i:
    sum_+=A[k]
    #print(sum_)
  if np.all(sum_[1:]>=x) and min_>sum_[0]:
    min_ = sum_[0]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m,x = map(int,input().split())
c = []
a = []
for i in range(n):
  l = list(map(int,input().split()))
  c.append(l[0])
  a.append(l[1:])
result = -1
for i in range(2 ** n):
  ct = 0
  at = [0] * m
  for b in range(1, n + 1):
    bb = 1 << b
    if i & bb > 0:
      ct += c[b - 1]
      for j in range(0, m):
        at[j] += a[b - 1][j]
  if result == -1 or ct < result:
    r = 1
    for ati in at:
      if ati < x:
        r = 0
    if r == 1:
      result = ct
print(result)

Submission status: Wrong Answer

Solution code:
n,m,x = map(int,input().split())
c = []
a = []
for i in range(n):
  l = list(map(int,input().split()))
  c.append(l[0])
  a.append(l[1:])
result = -1
for i in range(2 ** n):
  ct = 0
  at = [0] * m
  for b in range(1, n + 1):
    if i & b > 0:
      ct += c[b - 1]
      for j in range(0, m):
        at[j] += a[b - 1][j]
  if result == -1 or ct < result:
    r = 1
    for ati in at:
      if ati < x:
        r = 0
    if r == 1:
      result = ct
print(result)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n,m,x = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
ans = 10**9 + 1
for i in range(2 ** n):
  skill = [0] * m
  overTen = False
  money = 0
  for j in range(n):
    if ((int(bin(i)[2:]) >> j) & 1):
      money += a[j][0]
      for h in range(m):
        skill[h] += a[j][h+1]
  for k in skill:
    if k >= x:
      overTen = True
    else:
      overTen = False
      break
  if overTen == True:
    if money < ans:
      ans = money
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

books = []

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

patern = []

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

cost = 10**6


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

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

Submission status: Wrong Answer

Solution code:
import itertools

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

books = []

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

patern = []

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

cost = 10**6


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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

ans = 10**5 + 1

for i in range(2 ** n):
  skill = [0] * m
  overTen = False
  money = 0
  for j in range(n):
    if ((int(bin(i)[2:]) >> j) & 1):
      money += a[j][0]
      for h in range(m):
        skill[h] += a[j][h+1]
  for k in skill:
    if k >= x:
      overTen = True
    else:
      overTen = False
      break

  if overTen == True:
    if money < ans:
      ans = money

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#import time

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

    return -1 if mi == 100000000000000000000 else mi

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

Submission status: Wrong Answer

Solution code:
#import time

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

    return -1 if mi == 100000000000000000000 else mi

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#import time

def main():
	N, M, X = map(int, input().split())
	c = [list(map(int, input().split())) for _ in range(N)]
	c = sorted(c, key = lambda x: x[0])
	kekka = [0]*(M+1)
	#for i in range(N):
	#    c[i].insert(0, sum(c[i][1:]))
	ans = -1
	for i in range(N):
		for j in range(M+1):
			kekka[j] += c[i][j]
	#print(kekka)
	#for i in range(1,M+1):
	#    if kekka[i] < X:
	for i in range(1, M+1):
		if kekka[i] < X:
			return -1


	for i in range(N-1, 0, -1):
		for j in range(1, M+1):
			if kekka[j] - c[i][j] >= X:
				kekka[j] -= c[i][j] 
				if j == M:
					kekka[0] -= c[i][0]
			else:
				break
	return kekka[0]

	#for i in range(N):
	#    for j in range(i+1, N):



	#print(*c, sep='\n')


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

Submission status: Wrong Answer

Solution code:
# C Skill Up

def list_add(li1, li2):
  return [a+b for a, b in zip(li1, li2)]

N, M, X = map(int, input().split())
data = []
for n in range(N):
  data.append(list(map(int, input().split())))

ans = 100000 * N
for c in range(1 << N):
  x = [0] * M
  yen = 0
  for i, n in enumerate(format(c, f"{N}b")):
    if n == "1":
      yen += data[i][0]
      x = list_add(x, data[i][1:])
  for xm in x:
    if xm < X:
      break
  else:
    ans = min(ans, yen)
    
if ans == 100000 * N:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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

min = float('inf')

for i in range(1<<n): # 1<<n == 2**n
    study = [0 for _ in range(m)]
    cost = 0

    for j in range(n):
        if i&(1<<j):
            cost += a[j][0]
            study = [study[k]+a[j][k] for k in range(m)]

    if(all([s >= x for s in study])):
        if min > cost:
            min = cost

if float('inf') > min:
    print(min)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import copy
from collections import deque


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

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


t = deque()
t.append([0 for _ in range(m+1)])

min = float('inf')

def study_finished(algos):
    result = True
    for i in range(m):
        if algos[i] < x:
            result = False
    return result

for i in range(n):
    loop_num = len(t)
    for _ in range(loop_num):
        tmp = t.popleft()
        tmpd = copy.deepcopy(tmp)

        t.append(tmpd)

        for j in range(len(tmp)):
            if j == 0:
                tmp[0] += c[i]
            else:
                tmp[j] += a[i][j-1]

        if study_finished(tmp):
            if min > tmp[0]:
                min = tmp[0]
        else:
            t.append(tmp)

if float('inf') > min:
    print(min)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import product
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
A.insert(0,[0 for _ in range(M+1)])
flag = 0
for j in range(1,M+1):
    cnt = 0
    for i in range(1,N+1):
        cnt += A[i][j]
    if cnt<X:
        flag = 1
        break
if flag==1:
    cost = -1
else:
    cost = 10**7
    for x in product((0,1),repeat=N+1):
        if x[0]==0:
            flag = 0
            cnt = 0
            for j in range(1,M+1):
                for i in range(1,N+1):
                    if x[i]==1:
                        cnt += A[i][j]
                if cnt<X:
                    flag=1
                    break
            if flag==0:
                cnt = 0
                for i in range(1,N+1):
                    if x[i]==1:
                        cnt += A[i][0]
                cost = min(cost,cnt)
print(cost)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
n,m,x = map(int, input().split())
ca = np.zeros((n,m+1))
for i in range(n):
    ca[i] = [int(i) for i in input().split()]

p = itertools.product([True,False], repeat = n)
ans_l = []
for i in p:
    ca_cut = ca[i,:]
    if len(ca_cut) == 0: 
        continue
    ca_cut_sum = ca_cut.sum(axis=0)
    if all(ca_cut_sum[1:] >= x):
        ans_l.append(ca_cut_sum[0])
if len(ans_l) == 0:
    ans = -1
else:
    ans = min(ans_l)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
n,m,x = map(int, input().split())
ca = np.zeros((n,m+1))
for i in range(n):
    ca[i] = [int(i) for i in input().split()]

'''
N行を読む or 読まないで全探索する
itertools.productでTrue,Falseの全組み合わせリストを生成し、
Numpyのブールインデックス参照で本を選択する
'''
p = itertools.product([True,False], repeat = n)
ans = []
for i in p:
    ca_cut = ca[i,:]
    if len(ca_cut) == 0: 
        continue
    ca_cut_sum = ca_cut.sum(axis=0)
    if all(ca_cut_sum[1:] >= x):
        ans.append(ca_cut_sum[0])
if len(ans) == 0:
    ans = -1
else:
    ans = min(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
n,m,x = map(int, input().split())
ca = np.zeros((n,m+1))
for i in range(n):
    ca[i] = [int(i) for i in input().split()]

'''
N行を読む or 読まないで全探索する
itertools.productでTrue,Falseの全組み合わせリストを生成し、
Numpyのブールインデックス参照で本を選択する
'''
p = itertools.product([True,False], repeat = n)
ans = []
for i in p:
    ca_cut = ca[i,:]
    ca_cut_sum = ca_cut.sum(axis=0)
    if all(ca_cut_sum[1:] >= x):
        ans.append(ca_cut_sum[0])
if len(ans) == 0:
    ans = -1
else:
    ans = min(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m,x=map(int,input().split())
P = [list( map( int, input().split() ) ) for i in range(n)]
ca=np.array(P).reshape((n,m+1))
value= 10000000
for i in range(2**n+1):
  sum=np.empty(m+1)
  for y in range(n):
    if (i >> y & 1) == 1:
      sum= sum + ca[-y,:]
  summ=sum[1:]
  if all(elm >= x for elm in summ) == True:
    value= min(int(sum[0]), value)
if value==10000000:
  print('-1')
else:
  print(value)

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
ans = []
books = []
for i in range(n):
  a = list(map(int, input().split()))
  books.append(a)
  
for i in range(2**n):
  _trigger = True
  _sum = [0 for k in range(m+1)]
  for j in range(n):
    if ((i >> j) & 1):
      for k in range(m+1):
        _sum[k] += books[j][k]
  for j in range(1, m):
    if _sum[j] < x:
      _trigger = False
      
  if (_trigger == True):
      ans.append(_sum[0])
    
if (len(ans) == 0):
  print (-1)
else:
  print (min(ans))

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
ans = 10000001
books = []
for i in range(n):
  a = list(map(int, input().split()))
  books.append(a)
  
for i in range(2**n):
  _trigger = True
  _sum = [0 for k in range(m+1)]
  for j in range(n):
    if ((i >> j) & 1):
      for k in range(m+1):
        _sum[k] += books[j][k]
  for j in range(1, m):
    if _sum[j] < x:
      _trigger = False
      
  if (_trigger == True and ans > _sum[0]):
      ans = _sum[0]
    
if (ans == 10000001):
  print (-1)
else:
  print (ans)

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
ans = [100001 for k in range(m+1)]
books = []
for i in range(n):
  a = list(map(int, input().split()))
  books.append(a)
  
for i in range(2**n):
  _trigger = True
  _sum = [0 for k in range(m+1)]
  for j in range(n):
    if ((i >> j) & 1):
      for k in range(m+1):
        _sum[k] += books[j][k]
  for j in range(1, m):
    if _sum[j] < x:
      _trigger = False
      
  if (_trigger == True and ans[0] > _sum[0]):
    for j in range(m+1):
      ans[j] = _sum[j]
    
if (ans[0] == 100001):
  print (-1)
else:
  print (ans[0])