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:
#!/usr/bin/env python3
# coding: utf-8
import itertools

def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

def main():
    N, M, X = map(int, input().split())
    a = []
    t = []
    for i in range(N):
        a.append(list(map(int, input().split())))
    for i in range(1, N):
        c = itertools.combinations(range(N), i)
        # debug(list(c))
        for cc in c:
            # debug(cc)
            tt = [0 for _ in range(M + 1)]
            for x in cc:
                # debug(x)
                for j in range(M + 1):
                    tt[j] += a[x][j]
                if sorted(tt[1:])[0] >= X:
                    t += tt[0],
    s = -1 if len(t) == 0 else sorted(t)[0]
    print(s)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

lst.sort(key=lambda x: sum(x[1:]) ,reverse=True)

rikaido = [0]*m
rikaido_check1 = [0]*m

rikaido2 = [0]*m
rikaido_check2 = [0]*m

ans1 = 0
ans2 = 0

check1 = 0
for i in lst:
    for j in range(m):
        rikaido[j] += i[j+1]
        if rikaido[j] >= x:
            rikaido_check1[j] = 1
    ans1 += i[0]
    if sum(rikaido_check1) == m:
        check1 = 1
        break

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

check2 = 0
for i in lst:
    for j in range(m):
        rikaido2[j] += i[j+1]
        if rikaido2[j] >= x:
            rikaido_check2[j] = 1
    ans2 += i[0]
    if sum(rikaido_check2) == m:
        check2 = 1
        break

if check1 == check2 == 0:
    print("-1")
elif check1 == 0 and check2 != 0:
    print(ans2)
elif check1 != 0 and check2 == 0:
    print(ans1)
else:
    print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import numpy as np
# スペース区切りの整数入力
N,M,X = map(int, input().split())

a = np.zeros((N,M+1))

for i in range(N):
    # スペース区切りの整数をリストに入力
    a[i] = [int(x) for x in input().split()]

b = np.zeros(N)
c = np.zeros(M+1)
min_cost = 9999999999999999

for i in range(2**N):
    ii = i
    for j in range(N):
        b[j] = ii % 2
        ii = ii // 2
    c = np.zeros(M+1)
    flg = "ok"
    for k in range(M+1):
        for j in range(N):
            c[k] += a[j,k] * b[j]
        if k > 0 and c[k] < X:
            flg = "ng"
            continue
    if flg == "ok":
        min_cost = min(min_cost,c[0])

if min_cost == 9999999999999999:
    print(-1)
else:
    print(min_cost)

Submission status: Wrong Answer

Solution code:
# 1<= N,M <=12
# 1<= X <=10**5
# 1<= C <= 10**5
# 0<= A <=10**5
from itertools import combinations
N, M, X = map(int, input().split())

books = [list(map(int, input().split())) for _ in range(N)]
min_cost = float('inf')
test_cost = min_cost
# print(books)
for i in range(1, M + 1):
    combies = list(map(list, (combinations(list(range(N)), i))))
    # print(combies)
    for combi in combies:
        cost = 0
        skills = [0 for _ in range(M)]
        for book_i in combi:
            cost += books[book_i][0]
            for skill_i, skill_point in enumerate(books[book_i][1:]):
                skills[skill_i] += skill_point
        # print(cost, skills)
        ok = True
        for skill_point in skills:
            if skill_point < X:
                ok = False
                break
        if ok:
            min_cost = min(min_cost, cost)
if min_cost == test_cost:
    print(-1)
else:
    print(min_cost)

Submission status: Wrong Answer

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

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

ans = 999999
for i in range(1, N+1):
    for pair in itertools.combinations(values_list, i):
        this_m_dict = {}
        this_cost = 0
        for item in pair:
            for j in range(1, M+1):
                this_m_dict[j] = this_m_dict.get(j, 0) + item[j]
            this_cost += item[0]
        for myvalue in this_m_dict.values():
            if myvalue < X:
                break
        ans = min(this_cost, ans)

print(ans)

Submission status: Wrong Answer

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

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

kingakumin = 10000000000

for i in range(2 ** n):
    now = []
    inow = i
    for j in range(n):
        now.append(i % 2)
        i = i // 2

    syuutoku = []
    for j in range(m):
        syuutoku.append(0)

    kingaku = 0
    for j in range(n):
        if now[j] == 1:
            kingaku = kingaku + cas[j][0]
            for k in range(m):
                syuutoku[k] = syuutoku[k] + cas[j][k + 1]

    flag = True
    for j in range(m):
        if syuutoku[j] < x:
            flag = False

    if flag and kingakumin > kingaku:
        kingakumin = kingaku

print(kingakumin)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
N,M,X=map(int, input().split())
book = []
for _ in range(N):
    book.append(list(map(int, input().split())))
book = np.array(book)
money=pow(10,6)
for i in itertools.product([0,1], repeat=N):
    book2=book
    dellist = []
    for n,l in enumerate(i):
        if l==0:
            dellist.append(n)
    book2=np.delete(book2, dellist, 0)
    ansar = np.sum(book2,axis=0)
    if np.sum(ansar[1:]>=X)==M:
        if money>ansar[0]:
            money = ansar[0]
if money == pow(10,6):
    print(-1)
else:
    print(money)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,x=list(map(int,input().split()))
ans=10**5
A=[list(map(int,input().split())) for i in range(n)]
B=sorted(A, key=lambda x: x[0])
#print(B)
D=[0]*(m+1)
for i, _ in enumerate(B, 1):
  for j in itertools.combinations(B,r=i):
    C=list(zip(*j))
#    print(C)
    for m in range(m+1):
      D[m]=sum(C[m])
#    print(D)
    E=[i for i in D[1:] if i>=x ]
    if len(E)==m:
      ans=min(ans,D[0])
print(ans) if ans!=10**5 else print(-1)

Submission status: Wrong Answer

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

z = [i for i in range(1, N)]
m = [1000000000000000000]

for i in range(N):
    x = list(itertools.combinations(z,i+1))

    for s in x:
        for k in range(1,M+1):
            C = sum(A[j-1][k] for j in s)
            if C < X:
                break
        else:
            m.append(sum(A[o-1][0] for o in s))
print(min(m) if min(m)!=1000000000000000000 else -1)

Submission status: Wrong Answer

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

for i in range(n):
    a=list(map(int,input().split()))
    l.append(a)
print(l)
ans=99999999
for i in range(2 ** n):
    bag = []
    for j in range(n):  
        if ((i >> j) & 1): 
            bag.append(l[j])  
    skill=[0]*m
    enou=[0]*m
    mone=0
    for sub in bag:
        mone+=sub[0]
        for kk in range(1,m):
            skill[kk-1]+=sub[kk]
            if skill[kk-1]>=x:
                enou[kk-1]+=1
    if sum(enou)==m:
        if ans>mone:
            ans=mone
if ans==99999999:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def judge_understand(us_algo, M, X):
    for i in range(M):
        if us_algo[i] < X:
            return False

    return True


def main():
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split())) for _ in range(N)]
    CA.sort()
    ans = 10 ** 5 + 1
    Cmoney = 0

    for i in range(N):
        understand_algo = [0] * M
        Cmoney = 0

        for j in range(i, N):

            for k in range(M):
                understand_algo[k] = understand_algo[k] + int(CA[j][k + 1])

            Cmoney = Cmoney + int(CA[j][0])
            if judge_understand(understand_algo, M, X):
                ans = min(ans, Cmoney)
                break

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


main()

Submission status: Wrong Answer

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

book = [0]*N

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

sorted_book = sorted(book)

A_list = [0]*(M) #各列ごとに初めて能力が10を超える行数を判定して数値を入れていく
for j in range(1, M+1):
    A_sum = 0
    count = 0

    for i in range(N):
        A_sum += sorted_book[i][j]
        count +=1
        if A_sum >= X:
            break
    
    if A_sum < X:
        A_list[j -1] = -1
    else:
        A_list[j -1] = count


answer = 0
if -1 in A_list:
    answer = -1
else:
    max_A_list = max(A_list)
    for i in range(max_A_list):
        answer += sorted_book[i][0]

print(A_list)
print(answer)

Submission status: Wrong Answer

Solution code:
import itertools
def chkx(a,m,x):
  ach = 1
  for i in range(m):
    if a[i] < x:
      ach = 0
  return ach==1
  
n,m,x = map(int,input().split())
a = [[]]*n
for i in range(n):
  a[i] = list(map(int,input().split()))
ax = [0]*m
mincost = 0
for i in range(n):
  for j in range(m):
    ax[j] += a[i][j+1]
  mincost += a[i][0]
if not chkx(ax,m,x):
  print(-1)
else:
  toiter = list(range(1,n))
  for i in range(1,n):
    coms = list(itertools.combinations(toiter,i))
    for j in range(len(coms)):
      ax = [0]*m
      curcost = 0
      for k in range(len(coms[j])):
        for l in range(m):
          ax[l] += a[coms[j][k]][l+1]
        curcost += a[coms[j][k]][0]
      if chkx(ax,m,x):
        mincost = min(mincost,curcost)
  print(mincost)

Submission status: Wrong Answer

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

sumnum = 0
for i in range(n):
  ave = (sum(list[i]) - list[i][0]) / list[i][0]
  list[i].append(ave)
  
sortedList = sorted(list, key=lambda x:(x[m + 1]), reverse=True)

res = [0] * m
index = 1
for i in range(n):
  isOver = True
  for j in range(m):
    #isOver = True
    res[j] = res[j] + sortedList[i][j + 1]
    if res[j] < x:
      isOver = False
      
  if isOver == True:
    total = 0
    for k in range(i + 1):
      total = total + sortedList[k][0]
    print(total)
    break
    
if isOver == False:
  print(-1)

Submission status: Wrong Answer

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

z = [i for i in range(1, N)]
m = [1000000000000000000]

for i in range(N):
    x = list(itertools.combinations(z,i+1))
    print(x)
    for s in x:
        for k in range(1,M+1):
            C = sum(A[j-1][k] for j in s)
            if C < X:
                break
        else:
            m.append(sum(A[o-1][0] for o in s))
print(m)
print(min(m) if min(m)!=1000000000000000000 else -1)

Submission status: Wrong Answer

Solution code:
import numpy as np


N, M, X = map(int, input().split())
wv = np.array([tuple(map(int, input().split())) for i in range(0, N) ])

x_list = np.array([ X for i in range(M)])
# print(wv)
# print(x_list)

#安い順に
wv = wv[np.argsort(wv[:,0])]
# print(wv)

def rec(n, uplimit_x):
    ans = 0

    #最後の本までいってだめだった場合
    if n == N:
        return 10**10

    # print(n)
    # print(uplimit_x - wv[n][1:])
    # n番目の品物を買って最後の場合(熟練度Xをすべて超えた場合)
    if (np.all(uplimit_x - wv[n][1:] <= 0)):
        # print(ans,n, uplimit_x - wv[n][1:],"Yes!")
        return wv[n][0]

    # n番目の品物が使える時
    # -> n番目の品物は買った方がいいのか、買わない方がいいのか...?
    else:
        ans = min(
        rec(n + 1, uplimit_x), #買わない
        rec(n + 1, uplimit_x - wv[n][1:]) + wv[n][0] #買う
        )
        # print(ans,n, uplimit_x)
    return ans

def solve():
    ans = rec(0,x_list)
    if ans >= 10**5:
        print(-1)
    else:
        print(ans)

def main():
    solve()

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from itertools import chain, combinations

N, M, X = [int(n) for n in input().split()]

matrix = np.zeros((N,M+1))
for i in range(N):
    matrix[i] = np.array([int(n) for n in input().split()])

total = np.sum(matrix[:,1:],axis=0)
if not all(i >= X for i in total):
    print(-1)
    sys.exit(0)

def checkthresh(A, thresh):
    return all(i >= thresh for i in A)

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

cost = 10**5
for subset in powerset(range(N)):
    sum_subset = np.zeros((1,M+1))
    for i in subset:
        sum_subset += matrix[i,:]
    sum_subset = sum_subset[0]
    if checkthresh(sum_subset[1:], X):
        cost = min(cost, sum_subset[0])

print(int(cost))

Submission status: Wrong Answer

Solution code:
# 1<= N,M <=12
# 1<= X <=10**5
# 1<= C <= 10**5
# 0<= A <=10**5
from itertools import combinations
N, M, X = map(int, input().split())

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

# print(books)
for i in range(1, M + 1):
    combies = list(map(list, (combinations(list(range(N)), i))))
    # print(combies)
    for combi in combies:
        cost = 0
        skills = [0 for _ in range(M)]
        for book_i in combi:
            cost += books[book_i][0]
            for skill_i, skill_point in enumerate(books[book_i][1:]):
                skills[skill_i] += skill_point
        # print(cost, skills)
        ok = True
        for skill_point in skills:
            if skill_point < X:
                ok = False
                break
        if ok:
            min_cost = min(min_cost, cost)
if min_cost == float('inf'):
    print(-1)
else:
    print(min_cost)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

N,M,X= map(int, input().split())
C =[]
A =[]
ans = []
ANS =[]
count = 0

for i in range(N):
    C = list(map(int,input().split()))
    A.append(C)
for i in range(1,N+1):
    L = list(itertools.combinations(A, i))
    L = np.array(L)
    for i in L:
        Z=np.array([0]*(M+1))
        for j in i:
            Z = Z + j
            flag = False
        ans.append(Z)
for i in ans:
    for j in range(1,M+1):
        if(i[j] < X):
            break
        if(i[j] >= X):
            count += 1
        ANS.append(i)
ANS.sort(key=lambda x: x[0])
if count == 0:
    print(-1)
    exit(0)
print(ANS[0][0])

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**10000
for i in range(N+1):
    a=list(combinations(C,i))
    for s in a:
        print(s)
        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**10000 else ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

n,m,x=map(int,input().split())
li=[list(map(int,input().split())) for i in range(n)]
li=np.array(li)
y=np.sum(li, axis=0)
if(np.min(y[1:])<x):
    print(-1)

def check(i):
    a=list(itertools.combinations(range(n), i))
    
    ans=(10**5)*n
    for j in a:
        b=[0]*(m+1)
        for s in j:
            b+=li[s]
            
        #print(np.min(b[1:]))
        if(np.min(b[1:])>=x) and ans>b[0]:
            ans=b[0]
    return(ans)

for i in range(1,n+1):
    ans=check(i)
    if(ans>0 and ans!=(10**5)*n):
        print(ans)
        break
    if(i==n):
        print(-1)

Submission status: Wrong Answer

Solution code:
print('-1')

Submission status: Wrong Answer

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

b = [i for i in range(N)]
n = len(b)

b_pairs = []
for i in range(1, n+1):
    b_pairs += list(itertools.combinations(b, i))

cnt = 0
A = [0] * M
B = []
C = []
for i in range(2 ** N - 1):
  w = len(b_pairs[i])
  for j in range(M):
    for k in range(w):
      A[j] += l[b_pairs[i][k]][j + 1]
  B.append(A)
  A = [0] * M
  
for i in range(2 ** N - 1):
  w = len(b_pairs[i])
  for k in range(w):
    cnt += l[b_pairs[i][k]][0]
  C.append(cnt)
  cnt = 0

for i in range(len(B)):
  for j in range(M):
    if B[i][j] >= X:
      pass
    else:
      B[i] = 0
      break

for i in range(len(B)):
  if B[i] != 0:
    break
  else:
    print(-1)

for i in range(len(B)):
  if B[i] != 0:
    B[i] = C[i]
  else:
    B[i] = 1000000000000

print(min(B))

Submission status: Wrong Answer

Solution code:
import itertools
N,M,X=map(int,input().split())
A=[0]*(N);C=[0]*(N);c=0;D=[0]*(M);m=10**5;n=0;x=[];z=0;R=[0]*N;f=-1;cost=10**5;p=0
for i in range(N):
  S=list(map(int,input().split()))
  C[i]=S[0]
  A[i]=S[1:len(S)]
#print(C)
#print(A)
for i in range(len(C)):
  x.append(i)

for i, _ in enumerate(x, 1):     
    for j in itertools.permutations(x, r=i):
        for k in x:
          for l in range(M):
            D[l]=D[l]+A[k][l]
        for v in range(M):
          if D[v]<X:
            f=1
        if f!=1:
          for y in x:
            p=p+C[y]
            if p<cost:
              cost=p
          p=0
print(cost if cost!=100000 else -1)

Submission status: Wrong Answer

Solution code:
import numpy as np

i = list(map(int, input().split()))
N = i[0]
M = i[1]
X = i[2]

a = np.zeros((N, M+1))

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

x = np.sum(a, axis = 0)
x = x[1:]

if np.min(x) < X:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
import sys

num_list = [int(i) for i in input().split()]
book_list = np.array([[int(v) for v in input().split()] for i in range(num_list[0])])

sum_check = np.sum(book_list, axis=0)[1:]
if len(sum_check[sum_check < num_list[2]]) != 0:
    print('-1')
    
ok_list = []
for comb_num in range(1, num_list[0]+1):
    key_list = list(itertools.combinations([i for i in range(0, num_list[0])], comb_num))
    for key_val in key_list:
        sum_check = np.sum([book_list[i] for i in key_val], axis=0)
        if len(sum_check[1:][sum_check[1:] < num_list[2]]) == 0:
            ok_list.append(sum_check[0])
        else:
            pass
    if len(ok_list) != 0:
        print(min(ok_list))
        sys.exit()
    else:
        pass

Submission status: Wrong Answer

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

book = [0]*N

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

sorted_book = sorted(book)

A_list = [0]*(M) #各列ごとに初めて能力が10を超える行数を判定して数値を入れていく
for j in range(1, M+1):
    A_sum = 0
    count = 0

    for i in range(N):
        A_sum += sorted_book[i][j]
        count +=1
        if A_sum >= X:
            break
    
    if A_sum < 10:
        A_list[j -1] = -1
    else:
        A_list[j -1] = count


answer = 0
if -1 in A_list:
    answer = -1
else:
    max_A_list = max(A_list)
    for i in range(max_A_list):
        answer += sorted_book[i][0]

print(A_list)
print(answer)

Submission status: Wrong Answer

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

sumnum = 0
for i in range(n):
  ave = (sum(list[i]) - list[i][0]) / list[i][0]
  list[i].append(ave)
  
sortedList = sorted(list, key=lambda x:(x[m + 1]), reverse=True)
print(sortedList)

res = [0] * m
index = 1
for i in range(n):
  isOver = True
  for j in range(m):
    #isOver = True
    res[j] = res[j] + sortedList[i][j + 1]
    print(res)
    if res[j] < x:
      isOver = False
      
  if isOver == True:
    total = 0
    for k in range(i + 1):
      total = total + sortedList[k][0]
    print(total)
    break
    
if isOver == False:
  print(-1)

Submission status: Wrong Answer

Solution code:
# 1<= N,M <=12
# 1<= X <=10**5
# 1<= C <= 10**5
# 0<= A <=10**5
from itertools import combinations
N, M, X = map(int, input().split())

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

# print(books)
for i in range(1, M + 1):
    combies = list(map(list, (combinations(list(range(N)), i))))
    # print(combies)
    for combi in combies:
        cost = 0
        skills = [0 for _ in range(M)]
        for book_i in combi:
            cost += books[book_i][0]
            for skill_i, skill_point in enumerate(books[book_i][1:]):
                skills[skill_i] += skill_point
        # print(cost, skills)
        ok = True
        for skill_point in skills:
            if skill_point < X:
                ok = False
                break
        if ok:
            min_cost = min(min_cost, cost)
if min_cost == float('inf'):
    print('-1')
else:
    print(min_cost)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# coding: utf-8
import itertools

def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

def main():
    N, M, X = map(int, input().split())
    a = []
    t = []
    for i in range(N):
        a.append(list(map(int, input().split())))
    for i in range(1, N):
        c = itertools.combinations(range(N), i)
        # debug(list(c))
        for cc in c:
            # debug(cc)
            tt = [0 for _ in range(M + 1)]
            for x in cc:
                # debug(x)
                for j in range(M + 1):
                    tt[j] += a[x][j]
                if sorted(tt[:-1])[0] >= X:
                    t += tt[0],
    s = -1 if len(t) == 0 else sorted(t)[0]
    print(s)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

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

# print(N, M, X)
# print(C_A_list)

# N, M, X = 3, 3, 10
# C_A_list = [np.array([60, 2, 2, 4]),
#             np.array([70, 8, 7, 9]),
#             np.array([50, 2, 3, 9])]

price_min_list = []
for i in range(1, M + 1):
    for j in itertools.combinations(C_A_list, i):
        # print(j)
        sum_list = sum(j)
        if min(sum_list[1:]) >= X:
            price_min_list.append(sum_list[0])

if price_min_list:
    print(min(price_min_list))
else:
    print(-1)

Submission status: Wrong Answer

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

flag=True
flag2=True
i=1
champ=100000
total_cost=100000
while flag:
    newlist=list(itertools.combinations(range(N),i))
    for j in range(len(newlist)):
        for s in range(1,M+1):
            if sum(List[t][s] for t in newlist[j])<X:
                flag2=False
                break
        if flag2==True:    
            total_cost=sum(List[t][0] for t in newlist[j])
        if total_cost<champ:
            champ=total_cost
        flag2=True
    i=i+1
    if i==N+1:
        break

if champ==100000:    
    print(-1)
else:
    print(champ)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N,M,X=map(int,input().split())
ca=[]
for j in range(N):
    temp=list(map(int,input().split()))
    temp=temp+[j]
    ca.append(temp)
ju=[0]*M
for m in range(M):
    for n in range(N):
        ju[m]=ju[m]+ca[n][m+1]
ka=0
for m in range(len(ju)):
    if ju[m]<X:
      ka=1
if ka==1:
    print(-1)        
else:    
    ans=0
    count=[]
    for i in range(1,M+1):
        ca.sort(key=lambda x:x[i]/x[0],reverse=True)
        temp2=0
        for k in range(N):
            temp2=temp2+ca[k][i]
            count.append(ca[k][-1])
            if temp2>=X:
              break
    count=set(count)
    ca.sort(key=lambda x:x[-1])
    for i in count:
        ans=ans+ca[i][0]
    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)]



sums = 0
sum_num = 0

A.sort()

a = []

for i in range(N):
    for j in range(N):
        sums = sum(A[i][1:]) + sum(A[j][1:])
        
        if sums > X * M:
            sum_num = A[i][0] + A[j][0]
            a.append(sum_num)
    if sums < X * M:
        print('-1')
        break
    else:
        print(min(a))

Submission status: Wrong Answer

Solution code:

n, m, x = (int(x) for x in input().split())

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

# 値段の安い順に並び替え
book_list.sort()
# print(book_list)

ans = 0

skill_list = [0] * m

for j in range(n) :

    clear = True

    for i in range(m) :
        # print(' i :  {} '.format(i))
        skill_list[i] = skill_list[i] + book_list[j][i]

    for k in range(1, m) :
        # print(' skill_lise[k] :  {} '.format(skill_list[k]))
        if skill_list[k] < x :
            clear = False

    if clear == True :
        ans = skill_list[0]
        break

# まず条件不適を検索
# for j in range(m) :

#     sum = 0

#     print(' j :  {} '.format(j))

#     for i in range(n):

#         print(' i :  {} '.format(i))

#         sum = sum + book_list[i][j + 1]

#     print(' sum :  {} '.format(sum))

#     if sum <= x:
#         ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
def main():
  n,m,x=map(int,input().split())
  c=[[] for j in range(n)]
  a=[0]*m
  b=[0]*m
  for i in range(n):
    c[i]=list(map(int,input().split()))
  for k in range(1,m):
    b[k]=sum(map(lambda x: x[k], c))
    if b[k]<x:
      print(-1)
      exit()
  
  min_a0=sum(map(lambda x: x[0], c))
#print(a[0])
  b[0]=min_a0
  d=sorted(c,key=lambda x: x[0],reverse=True)
  a=copy.deepcopy(b)
  for y in range(n):
    a=copy.deepcopy(b)
    for p in range(y,n):
      for k in range(1,m):
    #print(p)
        a[k]-=d[p][k]
        if a[k]<x:
      #print(k)
          min_a0=min(a[0],min_a0)
          for q in range(k+1):
            a[q]+=d[p][q]
          break
      a[0]-=d[p][0]

  for y in range(n):
    a=copy.deepcopy(b)
    for p in range(y,n):
      for k in range(1,m):
    #print(p)
        a[k]-=c[p][k]
        if a[k]<x:
      #print(k)
          min_a0=min(a[0],min_a0)
          for q in range(k+1):
            a[q]+=c[p][q]
          break
      a[0]-=c[p][0]
      

  #print(a[0])
  print(min_a0)
main()

Submission status: Wrong Answer

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


total = [0 for _ in range(M)]
total_C = sum(C)
for a in A:
    for i in range(M):
        total[i] += a[i]

def check(t):
    for tt in t:
        if tt < X:
            return False
    return True

if not check(total):
    print(-1)
    exit()

import copy
while True:
    if max(C) == -1:
        break
    idx = C.index(max(C))
    tmp_total = copy.deepcopy(total)
    for i in range(M):
        tmp_total[i] -= A[idx][i]
    if check(tmp_total):
        total = tmp_total
        total_C -= C[idx]
    C[idx] = -1
print(total_C)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
import heapq

n,m,y = map(int, input().split())
cost=[]
for i in range(n):
    cost.append(list(map(int, input().split())))
    
cost_ar=np.array(cost)
iterable=list(range(n))
combinations=[]
for i in range(2,n+1):
    combinations.append(list(itertools.combinations(iterable,i)))
    
ans=[]

for i in combinations:
    for j in i:
        x=np.array([0]*(m+1))
        for k in j:
            x+=cost_ar[k]
        heapq.heappush(ans,x.tolist())

for i in cost:
  heapq.heappush(ans,i)
while len(ans) > 0:       
    temp = heapq.heappop(ans)
    for i in range(1,len(temp)):
        if temp[i]>=y:
          continue
        elif temp[i]<y:
            break
    if i==len(temp)-1:
        print(temp[0])
        break
    if len(ans)==0:
        print(-1)