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:
import itertools

def main():

    n,m,x = map(int,input().split())
    C = []
    A = []
    for i in range(n):
        array = list(map(int,input().split()))
        C.append(array[0])
        A.append(array[1:])
    cost = 10**6
    for i in range(1,n+1):
        combs = itertools.combinations(range(n), i)
        for comb in combs:
            skill = [0]*m
            cost_tmp = 0
            for e in comb:
                # print(comb)
                cost_tmp += C[e]
                for j in range(m):
                    skill[j] += A[e][j]
            for j in range(m):
                if skill[j] < x:
                    break
                if j == m-1:
                    print(cost_tmp, skill)
                    cost = min(cost, cost_tmp)
    if cost == 10**6:
        print(-1)
        return
    print(cost)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n, m, x = map(int, input().split())
a_list = []
for i in range(n):
	targets = list(map(int, input().split()))
	a_list.append(targets)
r_list = []
for i, _ in enumerate(a_list, 1):     
	for j in itertools.combinations(a_list, r=i):
		targets = [0] * (m+1)
		for t in j:
			k = 0
			for target in t:
				targets[k] += target
				k += 1
		if min(targets) >= x:
			r_list.append(targets)
if len(r_list) == 0:
	print(-1)
else:
	result = sorted(r_list, key=lambda x: x[0])
	print(result[0][0])

Submission status: Wrong Answer

Solution code:
import itertools

def list_add(in1, in2):
   return list(map(sum, zip(in1, in2)))

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

n = [i for i in range(N)]
c_sum = 0

for i in range(N):
    min_sum = 10e5
    flag = 0
    for v in itertools.combinations(n,i+1):
        c_sum = 0
        At = [0] * M
        for j in range(len(v)):
            At = list_add(At, A[v[j]])
            c_sum += C[v[j]]
        over10 = [k for k in At if k >= 10]
        if len(over10) == M:
            print(v)
            min_sum = min([min_sum, c_sum])
            flag = 1
    if flag == 1:
        print(min_sum)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
n,m,x=map(int,input().split())
C=[]
for _ in range(n):
    c=list(map(int,input().split()))
    if c[0]!= 0:
        c_weight=(sum(c[1:m])/c[0])
    else:
        c_weight=(sum(c[1:m]))

    c.append(c_weight)
    C.append(c)

C.sort(key=lambda x:-x[m+1])
price=0
clear=0
c_sum=[0]*m
for i in range(n):
    check=0
    for j in range(m):    
        c_sum[j] += C[i][j+1]
        if c_sum[j] >= x:
            check += 1
    price += C[i][0]
    if check >= m:
        print(price)
        clear=1
        break
if clear == 0:
    print('-1')

Submission status: Wrong Answer

Solution code:
from itertools import combinations
 
N, M, X = list(map(int,input().split()))
A = []
for i in range(N):
  A.append(list(map(int,input().split())))
sum = []
subsets=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        subsets.append(list(c))
 
for i in subsets:
  tmp = [0]*(M+1)
  if len(i) == 1:
    sum.append(i[0])
  elif len(i) == 0:
    sum.append([0]*(M+1))
  else:
    for j in i:
      tmp = list(map(lambda a,b: a + b, tmp,j))
    sum.append(tmp)
    
min_price = 1000000
 
for i in sum:
  t = 0
  for j in range(len(i)):
    if j==0:
      pass
    elif X > i[j]:
      t = 1
  if t == 0:
    min_price = min(min_price, i[0])
 
if min_price == 1000000:
  print(-1)
else:
  print(min_price)

Submission status: Wrong Answer

Solution code:
import numpy as np

N,M,X=map(int,input().split())
A=[[]for i in range(N+1)]
ans=10**6
for i in range(N):
    A[i]=(list(map(int,input().split())))
A=np.array(A)
#print(A)
for i in range(2**N):
    B=np.zeros(M+1)
    for j in range(N):
        if ((i >> j) & 1):
            B+=A[j]
    #print(B)
    if ans>=B[0] and X<=np.amin(B[1:]):
        ans=B[0]
if ans==10**6:
    print(-1)
    exit()
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq

n,k,x=list(map(int,input().split()))

c=np.array([list(map(int,input().split())) for _ in range(n)])
kumi=[i for i in range(n)]
ans=float("inf")
for k_n in range(n+1):
    t=itertools.combinations(kumi, k_n)
    if k_n<2:
        continue
    for each in t:
        cal=c[each,:].sum(axis=0)
        if min(cal)>=x:
            ans=min(cal[0],ans)
if ans==float("inf"):
    ans=-1
print(ans)

Submission status: Wrong Answer

Solution code:
def python_list_add(in1, in2):
  for i in range(len(in1)):
    in1[i] = in1[i] + in2[i]
  return in1
  
n, m, x = map(int, input().split())
a = []
for i in range(n):
  a.append(list(map(int, input().split())))
ans = []
s = [0]*(m+1)
s = python_list_add(s, a[0])
for i1 in range(2):
  for i2 in range(2):
    for i3 in range(2):
      for i4 in range(2):
        for i5 in range(2):
          for i6 in range(2):
            for i7 in range(2):
              for i8 in range(2):
                for i9 in range(2):
                  for i10 in range(2):
                    for i11 in range(2):
                      for i12 in range(2):
                        if i1 == 1 and n >= 1:
                          s = python_list_add(s, a[0])
                        if i2 == 1 and n >= 2:
                          s = python_list_add(s, a[1])
                        if i3 == 1 and n >= 3:
                          s = python_list_add(s, a[2])
                        if i4 == 1 and n >= 4:
                          s = python_list_add(s, a[3])
                        if i5 == 1 and n >= 5:
                          s = python_list_add(s, a[4])
                        if i6 == 1 and n >= 6:
                          s = python_list_add(s, a[5])
                        if i7 == 1 and n >= 7:
                          s = python_list_add(s, a[6])
                        if i8 == 1 and n >= 8:
                          s = python_list_add(s, a[7])
                        if i9 == 1 and n >= 9:
                          s = python_list_add(s, a[8])
                        if i10 == 1 and n >= 10:
                          s = python_list_add(s, a[9])
                        if i11 == 1 and n >= 11:
                          s = python_list_add(s, a[10])
                        if i12 == 1 and n >= 12:
                          s = python_list_add(s, a[11])
                        do = True
                        for j in s[1:]:
                          if j < x:
                            do = False
                            break
                          if do:
                            ans.append(s[0])
                        s = [0]*(m+1)
if len(ans) > 0:
  print(min(ans))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

ans = -1

num_list.sort(key=lambda x: x[0])

result = []
for n1 in range(1,len(num_list)+1):
    for conb in itertools.combinations(num_list, n1):
        result.append(np.sum(conb, axis=0))

for r in result:
    if min(r[1:]) >= x:
        print(r[0])
        exit()

print(ans)

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

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

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, M, X = In.ints()

cost = [0]*N
ach = [[0 for i in range(M)] for j in range(N)]

for i in range(N):
    ine = In.ints()
    cost[i] = ine[0]
    ach[i] = ine[1::]

res = 99999999999

def rec(idx, cost, ach, cur_ach, cur_cost, X):
    global res

    for i in range(len(ach[idx])):
        cur_ach[i] += ach[idx][i]

    cur_cost += cost[idx]

    if all([x>=X for x in cur_ach]):        
        res = min(res, cur_cost)
        return

    for i in range(idx+1, M):
        rec(i, cost, ach, cur_ach, cur_cost, X)

    cur_cost -= cost[idx]
    for i in range(len(ach[idx])):
        cur_ach[i] -= ach[idx][i]


for i in range(N):
    found = False    
    for comb in itertools.combinations([i for i in range(N)], i+1):        
        cur_cost = 0
        accum = [0]*M

        for el in comb:
            cur_cost+=cost[el]

            for j in range(M):
                accum[j] += ach[el][j]

            if all([x>=X for x in accum]):
                found=True
                res = min(res, cur_cost)
                break
    
    if found:
        break



if res == 99999999999:
    Out.int(-1)
else:
    Out.int(res)

######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import deque

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

sumA = [0]*M
for i in range(N):
  for j in range(M):
    sumA[j] += CA[i][j+1]

for i in range(M):
  if sumA[i] < X:
    print(-1)
    exit()

row = [i for i in range(1, N+1)]
ans = float("INF")
for i in range(1, M+1):
  for v in combinations(row, i):
    q = deque(v)
    cost = 0
    Asum = [0]*M
    while q:
      a = q.popleft() - 1
      cost += CA[a][0]
      for j in range(M):
        Asum[j] += CA[a][j+1]
    flag = True
    for m in range(M):
      if Asum[m] < X:
        flag = False
    if flag:
      ans = min(ans, cost)
      
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import*
N,M,X=map(int,input().split())
C=[list(map(int,input().split())) for i in range(N)]
ans=100**10
for i in range(N+1):
    a=list(combinations(C,i))
    for s in a:
        A=[0 for d in range(M)]
        flag=True
        for k in range(M):
            for u in range(len(s)):
                A[k]+=s[u][k]
        B=A[1:]
        for z in B:
            if z>=X:
                continue
            else:
                flag=False
                break
        if flag==True:
            ans=min(ans,A[0])
print(-1 if ans==100**10 else ans)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
import sys

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

for n in range(N):
  Y = list(map(int, input().split()))
  ALL.append(Y)

ALL = np.array(ALL)
ALL = ALL[np.argsort(ALL[:,0])]

ok_index = []
for n in range(N):
  for i in itertools.permutations(ALL, r=n+1):
      if n > 0:
        this_ar = np.sum(np.array(i), axis=0)
      else:
        this_ar = np.array(i)[0]
      if np.all(this_ar[1:]>=X):
        ok_index.append(this_ar[0])
        print(np.min(ok_index))
        sys.exit()
  # if len(ok_index) > 0:
  #   print(np.min(ok_index))
  #   sys.exit()
if len(ok_index)==0:
  print(-1)
else:
  print(np.min(ok_index))

Submission status: Wrong Answer

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

    c = sorted(c, key=lambda x: sum(x[1:]) / x[0], reverse=True)

    min_cost = 10000000000000000000
    for com in combinations(c, n):
        ans = [0] * m
        price = 0
        for i in com:
            p = i[1:]
            price += i[0]
            for n in range(len(ans)):
                ans[n] += p[n]

            if all([i >= x for i in ans]):
                if price < min_cost:
                    min_cost = price
                break
    if min_cost == 10000000000000000000:
        print(-1)
    else:
        print(min_cost)

resolve()

Submission status: Wrong Answer

Solution code:
def python_list_add(in1, in2):
  for i in range(len(in1)):
    in1[i] = in1[i] + in2[i]
  return in1
  
n, m, x = map(int, input().split())
a = []
for i in range(n):
  a.append(list(map(int, input().split())))
ans = []
s = [0]*(m+1)
s = python_list_add(s, a[0])
for i1 in range(2):
  for i2 in range(2):
    for i3 in range(2):
      for i4 in range(2):
        for i5 in range(2):
          for i6 in range(2):
            for i7 in range(2):
              for i8 in range(2):
                for i9 in range(2):
                  for i10 in range(2):
                    for i11 in range(2):
                      for i12 in range(2):
                        if i1 == 1 and n >= 1:
                          s = python_list_add(s, a[0])
                        if i2 == 1 and n >= 2:
                          s = python_list_add(s, a[1])
                        if i3 == 1 and n >= 3:
                          s = python_list_add(s, a[2])
                        if i4 == 1 and n >= 4:
                          s = python_list_add(s, a[3])
                        if i5 == 1 and n >= 5:
                          s = python_list_add(s, a[4])
                        if i6 == 1 and n >= 6:
                          s = python_list_add(s, a[5])
                        if i7 == 1 and n >= 7:
                          s = python_list_add(s, a[6])
                        if i8 == 1 and n >= 8:
                          s = python_list_add(s, a[7])
                        if i9 == 1 and n >= 9:
                          s = python_list_add(s, a[8])
                        if i10 == 1 and n >= 10:
                          s = python_list_add(s, a[9])
                        if i11 == 1 and n >= 11:
                          s = python_list_add(s, a[10])
                        if i12 == 1 and n >= 12:
                          s = python_list_add(s, a[11])
                        do = True
                        print(s)
                        for j in s[1:]:
                          if j < x:
                            do = False
                            break
                          if do:
                            ans.append(s[0])
                        s = [0]*(m+1)
if len(ans) > 0:
  print(min(ans))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n,m,x = map(int, input().split())
data_list = []
for i in range(n):
    data_list.append(list(map(int, input().split())))
    
base = 10000000
price = 12000000

for i in range(2 ** n):
    value_list = [0]*(m+1)
    value = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            value.append(data_list[j])

    for i in range(len(value)):
        for j in range(m+1):
            value_list[j] += value[i][j]

    if min(value_list[:-1]) >= x and value_list[0] < price:
        price = value_list[0]
    
    
if price == 12000000:
    print(-1)
else:
    print(price)

Submission status: Wrong Answer

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

# ca_array = sorted(ca_array, reverse=False, key=lambda x: x[0])  #[1]に注目してソート
resultMoney = -1
for i in range(len(ca_array)):
  tmpMoney = ca_array[i][0]
  m_array = [X for i in range(M)]
  for k in range(M):
    m_array[k] -= ca_array[i][k + 1]
  if sum(x > 0 for x in m_array) <= 0:
    resultMoney = tmpMoney
    break
  for j in range(i+1, len(ca_array)):
    tmpMoney += ca_array[j][0]
    for k in range(M):
      m_array[k] -= ca_array[j][k + 1]
    if sum(x > 0 for x in m_array) <= 0:
      resultMoney = tmpMoney
      break

print(resultMoney)

Submission status: Wrong Answer

Solution code:

N,M,X = map(int,input().split(" "))
# N冊、Xは目標値
CAList = []
for i in range(N):
    ca = list(map(int,input().split(" ")))
    CAList.append(ca)
CAList = sorted(CAList,reverse=True, key=lambda x: sum(x[1:])/x[0])

resultList = [0] * (M+1)
found = False
for a in CAList:
    resultList = [x + y for (x, y) in zip(resultList, a)]
    if min(resultList[1:len(a)]) >= X:
        print(resultList[0])
        found = True
        break

if not found:
    print("-1")

Submission status: Wrong Answer

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

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

nls = np.array(c)
f=0
if not all(np.sum(nls, axis=0) >= x):
    f = 1
    print(-1)   
else:
    import itertools
    import pprint
    result=[]
    final =[]
    for n in range(1,len(c)+1):
        for conb in itertools.combinations(c, n):
            result.append(list(conb))
    for l in result:
        l=np.array(l)
        tmp = np.sum(l, axis=0)
        # print("tmp", tmp)
        if all(tmp >= x):
            final.append(tmp.tolist())
    final.sort()
    print(final[0][0])

Submission status: Wrong Answer

Solution code:
def solve():
    N, M, X = map(int, input().split()) 
    import numpy as np
    arr = np.ones((N,M+1), int) * 1e18
    for i in range(N):
        arr[i] = list(map(int, input().split()))
    
    arr = arr[np.argsort(arr[:, 0])[::-1]]
    C = arr[:, 0].astype(int)
    arr = arr[:, 1:].astype(int)
    # print(C)
    # print(arr)

    if any(np.sum(arr, axis=0) < X):
        return -1

    i = 0
    for _ in range(N):
        if any(np.sum(np.delete(arr, i, axis=0), axis=0) < X):
            i += 1
        else:
            arr = np.delete(arr, i, axis=0)
            C = np.delete(C, i)

    return C.sum()


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

Submission status: Wrong Answer

Solution code:
from itertools import combinations
 
N, M, X = list(map(int,input().split()))
A = []
for i in range(N):
  A.append(list(map(int,input().split())))
sum = []
subsets=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        subsets.append(list(c))
 
for i in subsets:
  tmp = [0]*(M+1)
  if len(i) == 1:
    sum.append(i[0])
  elif len(i) == 0:
    sum.append([0]*6)
  else:
    for j in i:
      tmp = list(map(lambda a,b: a + b, tmp,j))
    sum.append(tmp)
    
min_price = 1000000
 
for i in sum:
  t = 0
  for j in range(len(i)):
    if j==0:
      pass
    elif X > i[j]:
      t = 1
  if t == 0:
    min_price = min(min_price, i[0])
 
if min_price == 1000000:
  print(-1)
else:
  print(min_price)

Submission status: Wrong Answer

Solution code:
n, m, x = list(map(int, input().split()))
books = []
dp = [[0]*(m+1) for i in range(2**n)]
for i in range(n):
    book = list(map(int, input().split()))
    books.append(book)

    
min_cost = -1


for i in range(2**n):
    if i == 0:
        continue
    refbook = 0
    keta = 0
    for j in range(12):
        if (i >> j) % 2 == 1:
            refbook += 2**j
            keta = j
        elif i >> j == 0:
            refbook -= 2**(keta)
            break
    refbook = max(0, refbook)   
    checker = True
    for k in range(m+1):
        dp[i][k] = dp[int(refbook)][k] + books[keta][k]
        if k != 0 and dp[i][k]<x:
            checker = False
            
    if checker:
        if min_cost == -1:
            min_cost = dp[i][0]
        else:
            min_cost = min(min_cost, dp[i][0])
         
print(min_cost)

Submission status: Wrong Answer

Solution code:
def python_list_add(in1, in2):
  for i in range(len(in1)):
    in1[i] = in1[i] + in2[i]
  return in1
  
n, m, x = map(int, input().split())
a = []
for i in range(n):
  a.append(list(map(int, input().split())))
ans = []
s = [0]*(m+1)
s = python_list_add(s, a[0])
for i1 in range(2):
  for i2 in range(2):
    for i3 in range(2):
      for i4 in range(2):
        for i5 in range(2):
          for i6 in range(2):
            for i7 in range(2):
              for i8 in range(2):
                for i9 in range(2):
                  for i10 in range(2):
                    for i11 in range(2):
                      for i12 in range(2):
                        if i1 == 1 and n >= 1:
                          s = python_list_add(s, a[0])
                        if i2 == 1 and n >= 2:
                          s = python_list_add(s, a[1])
                        if i3 == 1 and n >= 3:
                          s = python_list_add(s, a[2])
                        if i4 == 1 and n >= 4:
                          s = python_list_add(s, a[3])
                        if i5 == 1 and n >= 5:
                          s = python_list_add(s, a[4])
                        if i6 == 1 and n >= 6:
                          s = python_list_add(s, a[5])
                        if i7 == 1 and n >= 7:
                          s = python_list_add(s, a[6])
                        if i8 == 1 and n >= 8:
                          s = python_list_add(s, a[7])
                        if i9 == 1 and n >= 9:
                          s = python_list_add(s, a[8])
                        if i10 == 1 and n >= 10:
                          s = python_list_add(s, a[9])
                        if i11 == 1 and n >= 11:
                          s = python_list_add(s, a[10])
                        if i12 == 1 and n >= 12:
                          s = python_list_add(s, a[11])
                        do = True
                        print(s)
                        for j in s[1:]:
                          if j < x:
                            do = False
                            break
                          if do:
                            ans.append(s[0]+1)
                        s = [0]*(m+1)
if len(ans) > 0:
  print(min(ans))
else:
  print(-1)

Submission status: Wrong Answer

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

    c = sorted(c, key=lambda x: sum(x[1:]) / x[0], reverse=True)

    min_cost = 100000000000000
    for com in combinations(c, n):
        ans = [0] * m
        price = 0
        for i in com:
            p = i[1:]
            price += i[0]
            for n in range(len(ans)):
                ans[n] += p[n]

            if all([i >= x for i in ans]):
                if price < min_cost:
                    min_cost = price
                break
    if min_cost == 100000000000000:
        print(-1)
    else:
        print(min_cost)

resolve()

Submission status: Wrong Answer

Solution code:
import itertools

N, M, X = list(map(int, input().split()))
C = []
A = []

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

min_cost = 10 ** 7
flag_i = False
for i in range(1, N+1):
    comb_list = list(itertools.combinations(range(N), i))
    

    for comb in comb_list:
        know = [0] * M
        cost = 0
        for book in comb:

            for i in range(M):
                know[i] += A[book][i]
            cost += C[book]
        
        #達成チェック
        flag = True
        for i in range(M):
            if (know[i] < X):
                flag = False
              
        
        if (flag):
            flag_i = True
            
            if (min_cost > cost):
                min_cost = cost
if (flag_i):
    print(min_cost)
        

print(-1)

Submission status: Wrong Answer

Solution code:
N, M, X = map(int,input().split())
sum_list = [0]*(M+1)
CA = []
for i in range(N):
    a = list(map(int,input().split()))
    CA += [a]
    for j in range(M+1):
        if j == 0:
            CA[i][j] = -CA[i][j]
            sum_list[j] += CA[i][j]
        else:
            sum_list[j] += a[j]

CA.sort()#高い順に並べる
ans = -sum_list[0]

for ca in CA:
    for j in range(1,M+1):
        if sum_list[j] - ca[j] < X:
            break
            break
        else:
            sum_list[j] -= ca[j]
            if j == M:
                ans -= -ca[0]

#そもそも足りていないとき
for t in sum_list[1:M+1]:
    if t < X:
        ans = -1
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,copy

N,M,X = list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(N)]
C.sort(key=lambda x: x[0],reverse = True)
total = [0]*(M+1)
for c in C:
    total = [x + y for (x,y) in zip(total,c)]

def j(l):
    flg=0
    for r in l[1:]:
        if r < X:
            flg=1
    if flg:
        return True
    else:
        return False

if j(total):
    print(-1)
    sys.exit()

for i,c in enumerate(C):
    min = [x - y for (x,y) in zip(total,c)]
    if j(min)==False:
        total = copy.copy(min)

if j(min):
    print(total[0])
else:
    print(min[0])

Submission status: Wrong Answer

Solution code:
import itertools

n,m,x = map(int,input().split())
# a = [0 for i in range(m)]
ans = 0
tmp = 10 ** 7
ca = [[0]*m for i in range(n)]

for _ in range(n):
    ca[_] = list(map(int, input().split()))
print(ca)

xx = list(itertools.permutations(ca))


for cax in xx:
    ans = 0
    a = [0 for i in range(m)]

    for _ in range(n):
        cost = cax[_][0]
        chk = 0
        for i in range(m):
            a[i] += cax[_][i+1]
            if a[i] < x:
                chk = 1

        ans += cost
        if chk == 0:
            if tmp > ans:
                tmp = ans
            break
if tmp == 10 ** 7:
    print(-1)
    exit()
print(tmp)

Submission status: Wrong Answer

Solution code:
#C
import itertools
n, m, x = map(int, input().split())
ca = [list(map(int, input().split()))for i in range(n)]
l = []
ans=1e6
for i in range(1,n+1):
    for j in itertools.combinations(range(1, n + 1), i):
        # print(j)
        tmp=0

        li = [0] * m
        for k in j:
            # print(k)
            tmp+=ca[k-1][0]
            for o in range(m):
                # print(o)
                li[o] += ca[k - 1][o+1]
            # print(li)
        count = 0
        for p in li:
            # print(count)
            if p >= x:
                count += 1
            else:
                break
        # print(count,m)
        if count >= m:
            # print(count,m,j)
            ans = min(ans, tmp)
if ans != 1e6:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys



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

a=[]

s=[0]*m

money=0

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

  money+=A[0]

  for j in range(1,m+1):
    s[j-1]+=A[j]

for i in range(m):
  if s[i]<x:
    print("-1")
    sys.exit()

Submission status: Wrong Answer

Solution code:


def main():
    NMX = list(map(int,input().split()))

    CA = []

    for i in range(NMX[0]):
        CA.append(list(map(int,input().split())))

    CA.sort()
    CA.reverse()

    # print(CA)

    smA =[0] * (NMX[1]+1)

    for n in range(NMX[0]):
        for m in range(NMX[1]+1):
            smA[m] += CA[n][m]

    # print(smA)

    for n in range(NMX[0]):
        pre = []

        J = True


        for m in range(NMX[1]+1):
            if m == 0:
                pre.append(smA[m]-CA[n][m])
            else:
                pre.append(smA[m] - CA[n][m])

                if smA[m] - CA[n][m] < NMX[2]:
                    # print("yes")
                    J = False
                    break


        if J:
            smA = pre
        # print(smA)


    JU = True
    for i in range(len(smA)):
        if i == 0:
            continue
        else:
            if smA[i] < NMX[2]:
                JU = False

    if JU:
        print(smA[0])
    else:
        print("-1")


    # print(smA)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import combinations
n, m , x = map(int, input().split())
skill_dic = {} 
for i in range(n):
    tmp = list(map(int, input().split()))
    skill_dic[i] = {'cost':tmp[0],'skills':tmp[1:]}

def calc_cost(skill_books, skill_dic,x):
    skill_nums = len(skill_dic[0]['skills'])
    skills = np.zeros(skill_nums)
    for i in skill_books:
        skills += skill_dic[i]['skills']
    skills = skills.reshape(-1, skill_nums)
    if np.all(skills >= x): return sum([ skill_dic[skill_book]['cost'] for skill_book in skill_books ])
    return None 

i = 1
cost_list = []
while i < len(skill_dic.keys()):
    book_comb = combinations(skill_dic.keys(),i)
    for pattern in book_comb:
        cost = calc_cost(list(pattern),skill_dic, x)
        if cost is not None: cost_list.append(cost)
    i += 1
print(min(cost_list) if cost_list != [] else -1)

Submission status: Wrong Answer

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

num = pow(2, n)
min_cost = -1
for count in range(num):
    a_list = [0] * m
    cost = 0
    for i in range(n):
        bit = pow(2, i)
        if (count // bit) % 2 == 1:
            for j in range(m):
                a_list[j] = a_list[j] + list_ca[i][j + 1]
            cost += list_ca[i][0]
    if min(a_list) >= x:
        if min_cost == -1:
            min_cost = cost
        elif min_cost > cost:
            min_cost = cost
    print(a_list)

print(min_cost)