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
import numpy as np
n,m,x = map(int,input().split())
c = []
total = [0] * m
ans = float('inf')
finish = False
for i in range(n):
    c.append(list(map(int,input().split())))
for i in range(1,n+1):
    for comb in itertools.combinations(c,i):
        su = np.array(comb).sum(axis=0)
        if sum(su[1:] >= x) == m:
            ans = min(ans,su[0])
            finish = True
    if finish:
        break
if finish:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

def aryadd(ary):
    a = []
    for i in zip(*ary):
        a.append(sum(i))
    return a

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

ans = 10**10
for i in range(2, n+1):
    for j in combinations(a, i):
        sm = aryadd(j)
        if len(list(filter(lambda y: y >= x, sm[1:]))) >= m:
            if ans >= sm[0]:
                ans = sm[0]

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import combinations

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main(N,M,X,C, A):
    min_cost = 10**12
    combs = set()
    for i in range(N):
        for c in combinations(range(N), i):
            combs.add(c)

    for comb in combs:
        cost = 0
        xs = [0 for _ in range(M)]
        for c in comb:
            for i in range(M):
                xs[i] += A[c][i]
            cost += C[c]

        if all([x>=X for x in xs]):
            min_cost = min(min_cost, cost)

    if min_cost != 10**12:
        print(min_cost)
    else:
        print(-1)

    pass

if __name__ == '__main__':
    C = []
    A = []
    N, M, X = list(map(int, input().split()))
    for n in range(N):
        lst = list(map(int, input().split()))
        # for m in range(M):
        
        c = lst[0]
        a = lst[1:]

        C.append(c)
        A.append(a)

    
    main(N,M,X,C, A)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

NMX = input()
NMX = NMX.split()
N = int(NMX[0])
M = int(NMX[1])
X = int(NMX[2])

CA = []
for i in range(N):
    ca = input()
    ca = ca.split()
    CA.append(ca)

CA = np.array(CA, dtype = int)
C = CA[:,0]
A = CA[:,1:]

bb = np.array(list(itertools.product([0, 1], repeat = N)))


cost = 999999
for b in bb:
    AA = (A.T * b).T
    ss = np.sum(AA, axis=0)
    if np.all(ss >= X):
        CC = np.sum(C.T * b)
        if CC < cost:
            cost = CC

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

Submission status: Wrong Answer

Solution code:
def main():
    N,M,X  = map(int, input().split()) 
    C = []
    for _ in range(N):
        c=list(map(int, input().split()))
        C.append(c)
    
    min = -1

    for i in range(2 ** N):
        total = 0
        bag = []
        OK = False
        for j in range(N):  
            if ((i >> j) & 1):  
                bag.append(C[j])
        sumlist=[0]*M
        for j in range(len(bag)):
            for k in range(M):
                sumlist[k] += bag[j][k]
        for j in range(M-1):
            if(sumlist[j+1] < X):
                OK = False
                break
            else:
                OK = True
        if OK and (min==-1 or min > sumlist[0]):
            min = sumlist[0]

    print (min)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

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

U = [0] * (M + 1)
def rec(ans, pos):
    if pos == N:
        return ans
    row = Matrix[pos]
    for i in range(M  + 1):
        U[i] += row[i]

    for u in U[1:]:
        if u < X:
            break
    else:
        ans = min(U[0], ans)
        for i in range(M + 1):
            U[i] -= row[i]
        return ans

    ans = min(rec(ans, pos + 1), ans)
    for i in range(M  + 1):
        U[i] -= row[i]
    return min(rec(ans, pos + 1), ans)

ans = rec(float('inf'), 0)
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

caa_list = []

for i in range(n):
  c, *aa = map(int, input().strip().split())
  caa_list.append((c, aa))

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

for i in range(1, n+1):
  for caas in combinations(caa_list, i):
    sc = 0
    saa = [0] * m
    for c, aa in caas:
      sc += c
      for j in range(m):
        saa[j] += aa[j]
    if all(a >= x for a in saa):
      print(sc)
      exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import itertools
N,M,X=map(int,input().split())
ans=100001
List=[]
for _ in range(N):
  List.append([int(i) for i in input().split()])
for i in range(2,N):
  for j in itertools.combinations(range(N),i):
    tmp=[0]*(M+1)
    for k in j:      
      for l in range(M+1):
        tmp[l]+=List[k][l]
    if len([m for m in tmp[1:] if m>=X])==M:
      ans=min(ans,tmp[0])
if ans==100001:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

    row = []

    ans = 10 ** 6

    for i in range(N):
        row.append(list(map(int, input().split())))

    for k in range(1, N+1):
        co = list(combinations(row, k))

        for t in co:
            cost = 0
            skill = [0] * M
            for v in t:
                cost += v[0]
                for s in range(M):
                    skill[s] += v[s-1]

            if(min(skill) >= X):
                ans = min(ans, cost)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m,x = map(int,input().split())
ca = [list(map(int,input().split())) for i in range(n)]
c = []
import numpy as np
for i in range(n-1):
    for j in range(i+1,n):
        ai= np.array(ca[i])
        aj= np.array(ca[j])
        caa = ai + aj
        aa = caa[1:]
        l = [i for i in aa if i<x]
        if l == []:
            c.append(caa[0])

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

Submission status: Wrong Answer

Solution code:
import sys
import os
import itertools

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,M,X=map(int, input().split())
    C=[0]*N
    A=[[0 for j in range(M)] for i in range(N)]
    for i in range(N):
        tmp=list(map(int, input().split()))
        C[i]=tmp[0]
        A[i]=tmp[1:]

    sum=0
    min=100000000
    A_sum=[0]*M
    for i in range(N):
        for li in itertools.combinations(range(0,N),i+1):
            # print(li)
            sum=0
            A_sum=[0]*M
            for j in li:
                sum+=C[j]
                for l in range(M):
                    A_sum[l]+=A[j][l]
            # print(sum)
            for l in range(M):
                if A_sum[l]<X:
                    break
                if min>sum:
                    min=sum

    if min==100000000:
        print(-1)
    else :
        print(min)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n, m, x = map(int, input().split())
c = []
ans = []
mx = [0] * (m+1)
for _ in range(n):
    l = list(map(int, input().split()))
    c.append(l)
    for i in range(m+1):
        mx[i] += l[i]
if n%2 == 1:
    mid = (n+1)//2
else:
    mid = n // 2

for i in range(1, mid):
    for vl in itertools.permutations(c, i):
        a = [0] * m
        b = [0] * m
        p = 0
        for v in vl:
            p += v[0]
            for j in range(m):
                a[j] += v[1+j]
        flag = True
        for k in range(m):
            if a[k] < x:
                flag = False
        if flag:
            ans.append(p)
            
        flag = True
        for q in range(m):
            b[q] = mx[1+q] - a[q]
        for w in range(m):
            if b[w] < x:
                flag = False
        if flag:
            ans.append(mx[0] - p)
            
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Submission status: Wrong Answer

Solution code:
import itertools
N,M,X = map(int,input().split())
A=[]
ans=-1
for i in range(N):
    A.append(list(map(int,input().split())))
A.sort()
for n in range(1,len(A)+1):
    if ans==-1:
        for conb in itertools.combinations(A, n):
            S=[0]*(M+1)
            for L in conb:
                for i in range(M+1):
                    S[i] += L[i]
            if min(S[1:])>=X:
                ans=S[0]
                break
print(ans)

Submission status: Wrong Answer

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

cost_list = []
for choice in range(n):
  for v in itertools.combinations(ca, choice):
    cost = 0
    us = [0] * m
    for t in v:
      cost += t[0]
      for i in range(m):
        us[i] += t[i+1]
    flag = True
    for check in range(m):
      if us[check] < x:
        flag = False
    if flag == True:
      cost_list.append(cost)

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

Submission status: Wrong Answer

Solution code:
import itertools

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

l = [[int(i) for i in input().split()] for j in range(N)]

hoge = []
kouho = list(range(1,N+1))
for i in itertools.combinations_with_replacement(kouho, N):
    hoge.append(list(set(i)))

hoge = list(map(list, set(map(tuple, hoge))))

last_val = 100001
for ls in hoge:
    ls = list(set(ls))
    ans = [0] * M
    val = 0
    for a in ls:# a = [1,2]ながさM
        for ix,i in enumerate(l[a-1][1:]):
            ans[ix] += i
        val += l[a-1][0]
    b = [i for i in ans if i >= X]
    if len(b) == len(ans):
        last_val = min(last_val, val)

if last_val >= 100001:
    print(-1)
else:
    print(last_val)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
n,m,x = map(int, input().split())
book = list()*n
for i in range(n):
    temp = input().split()
    book.append(temp)

matrix = np.array(book, dtype="int")
decide = np.array(list(itertools.product([True,False],repeat=n)))
money = 1e6
for i in range(len(decide)):
    test = np.sum(matrix[np.where(decide[i,:]),:], axis = 0)
    test = np.sum(test, axis = 0)
    #print(test)
    #print(test[0])
    #print(np.sum(test[1:]>=x))
    if np.sum(test[1:]>=x) == m and money > test[0]:
        #print("koko")
        money = test[0]
if money == 1e6:
    print("-1")
else :
    print(money)

Submission status: Wrong Answer

Solution code:
# m 個のアルゴリズムを学びたい
# n 冊の参考書
# x 必要な理解度

n,m,x = map(int,input().split())
book = [list(map(int,input().split())) for _ in range(n)]
#n,m,x = 3,3,10
#book = [[60, 2, 2, 4], [70, 8, 7, 9], [50, 2, 3, 9]]

def listadd(a,b,n):
  c = [0] * n
  for i in range(n):
    c[i] = a[i]+b[i]
  return c

ans = 0
for candi in range(1,2**n): # 読む本の候補リスト
  s = [0] * (m + 1)
  ck = 1
  for i in range(n):
    #print(candi >> i & 1) 
    if candi >> i & 1:
      s = listadd(s,book[i],m+1)
  for j in range(m):
    if s[j] < x:
      ck = 0
      break
  if ck:
    if ans:
      ans = min(ans,s[0])
    else:
      ans = s[0]

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

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
(n, m, x) = tuple(map(int, input().split(" ")))
ca = np.array(
    [list(map(int, input().split(" "))) for i in range(n)]
)
c = -1
for i in range(n):
    itr = itertools.combinations(ca, i + 1)
    for v in itr:
        cv = np.sum(v, axis=0)
        if (cv[1:m] >= x).all() and (c == -1 or cv[0] < c):
            c = cv[0]
print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m, x = [int(k) for k in input().split()]
c = np.zeros(n, dtype=int)
a = np.zeros((n, m), dtype=int)
rikai_a = np.zeros(m, dtype=int)
for i in range(n):
    c[i], *a[i] = [int(k) for k in input().split()]
money = 0
used = []
finish = 0
for j in range(m):
    for i in np.argsort(a[:, j] / c[:])[::-1]:
        if rikai_a[j] >= x:
            finish += 1
            break
        rikai_a[j] += a[i][j]
        used.append(i)
if finish == m:
    used = list(set(used))
    print(sum([c[b] for b in used]))
else:
    print(-1)

Submission status: Wrong Answer

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

a=[]

for i in range(0,n):
    aa=input().split()
    for j in range(0,m+1):
        aa[j]=int(aa[j])
    a.append(aa)

smin=1000000*n
d=1000000*n


for i in range(0,2**n):
    mo=0
    x2=[1 for i2 in range(0,m)]
    
    for j in range(0,n):
        if ((i>>j)&1)==1:
            mo+=a[j][0]
            for k in range(0,m):
                x2[k]+=a[j][k+1]

    if min(x2)>=x:
        if mo<smin:
            smin=mo
    

if smin==d:
    print(-1)

else:
    print(smin)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

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

coin = []
for i in range(1, m+1):
  for v in itertools.combinations(books, i):
    comb = list(v)
    result = np.sum(comb, axis = 0)
    flag = True
    for j in range(1,m+1):
      if result[j] < x:
        flag = False
        break
    if flag:
      coin.append(result[0])

if len(coin) > 0:
  coin.sort(reverse=False)
  print(coin[0])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import os
import itertools

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,M,X=map(int, input().split())
    C=[0]*N
    A=[[0 for j in range(M)] for i in range(N)]
    for i in range(N):
        tmp=list(map(int, input().split()))
        C[i]=tmp[0]
        A[i]=tmp[1:]

    sum=0
    min=10000000
    A_sum=[0]*M
    for i in range(N):
        for li in itertools.combinations(range(0,N),i+1):
            # print(li)
            sum=0
            A_sum=[0]*M
            for j in li:
                sum+=C[j]
                for l in range(M):
                    A_sum[l]+=A[j][l]
            # print(sum)
            for l in range(M):
                if A_sum[l]<X:
                    break
                if min>sum:
                    min=sum

    if min==10000000:
        print(-1)
    else :
        print(min)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:


def solve():

    mini = 10**6
    combs = getcombs(n)
    for com in combs:
        skill = [0] * m
        price = 0
        for i in range(n):
            if int(com[i]):
                price += c[i]
                addvec(skill, a[i])
                if min(skill) >= x:
                    mini = min(mini, price)
    if mini!=10**6:
        print(mini)
    else:
        print(-1)
    return


def getcombs(n):
    combs = []
    for i in range(2**n):
        combs.append(format(i, '#0{}b'.format(n+2))[2:])
    return combs






def addvec(a,b):
    for i in range(len(a)):
        a[i] += b[i]


#s= input()
n,m, x = [int(i) for i in input().split(" ")]
c = []
a = []
for _ in range(n):
    read = [int(i) for i in input().split(" ")]
    c.append(read[0])
    a.append(read[1:])
solve()

Submission status: Wrong Answer

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

c=10**5+1
p=0
for i in range(1,2**(n+1)):
    al=[0]*m
    cost=0
    for j in range(n):
        if (i>>j)&1:
            for k in range(m):
                al[k]+=lis[j][k]
            cost+=lis[j][0]
    if min(al)>=x:
        c=min(c,cost)
        p=1
print(c) if p==1 else print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    n, m, x = MI()
    li = [LI() for _ in range(n)]

    min = float(inf)
    for i in range(2 ** n):
        flag = True
        total = [0] * (m + 1)
        for j in range(n):
            if (i >> j) & 1:
                total = [x + y for (x, y) in zip(total, li[j])]

        print(total)
        for t in total[1:]:
            if t < x:
                flag = False

        if flag:
            if total[0] < min:
                min = total[0]

    if isinstance(min, float):
        print(-1)
    else:
        print(min)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
(n, m, x) = tuple(map(int, input().split(" ")))
ca = np.array(
    [list(map(int, input().split(" "))) for i in range(n)]
)
c = (10**5) * n
for i in range(n):
    itr = itertools.combinations(ca, i + 1)
    for v in itr:
        cv = np.sum(v, axis=0)
        if (cv[1:m] >= x).all() and cv[0] < c:
            c = cv[0]
print(c)

Submission status: Wrong Answer

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

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


min_val = 10 ** 6

for bit in range(1 << N):
    this_ans = True
    R = [0] * M
    c = 0

    for i in range(N):
        if bit & (1 << i):
            c += C[i]
            for m in range(M):
                R[m] += A[i][m]

    for r in R:
        if r < X:
            this_ans = False

    if this_ans:
        min_val = min(min_val, c)


if min_val != 10 ** 6:
    print(min_val)
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(10**6)

INF = 10**10


def main(input, print):
    n, m, x = map(int, input().split())
    table = [[] for _ in range(n)]
    for i in range(n):
        table[i] = list(map(int, input().split()))
    ans = INF
    for i in range(1, n+1):
        p = itertools.combinations(range(n), i)
        for pj in p:
            t = 0
            mt = [0] * m
            for k in range(len(pj)):
                t += table[pj[k]][0]
                for l in range(m):
                    mt[l] += table[pj[k]][l+1]
            is_ok = True
            for l in range(m):
                if mt[l] < x:
                    is_ok = False
            if is_ok:
                ans = min(ans, t)
        if ans != INF:
            break
    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n,m,x=map(int,input().split())
b=[]
for i in range(0,n):
    b.append(list(map(int,input().split())))
flag=True
for i in range(0,m):
    count=0
    for bb in b:
        count=count+bb[i+1]
    if count<x:
        flag=False
        break
count=0
if m==1:
    b=sorted(b,key=itemgetter(1),reverse=True)
elif m==2:
    b=sorted(b,key=itemgetter(1,2),reverse=True)
elif m==3:
    b=sorted(b,key=itemgetter(1,2,3),reverse=True)
elif m==4:
    b=sorted(b,key=itemgetter(1,2,3,4),reverse=True)
elif m==5:
    b=sorted(b,key=itemgetter(1,2,3,4,5),reverse=True)
elif m==6:
    b=sorted(b,key=itemgetter(1,2,3,4,5,6),reverse=True)
elif m==7:
    b=sorted(b,key=itemgetter(1,2,3,4,5,6,7),reverse=True)
elif m==8:
    b=sorted(b,key=itemgetter(1,2,3,4,5,6,7,8),reverse=True)
elif m==9:
    b=sorted(b,key=itemgetter(1,2,3,4,5,6,7,8,9),reverse=True)
elif m==10:
    b=sorted(b,key=itemgetter(1,2,3,4,5,6,7,8,9,10),reverse=True)
elif m==11:
    b=sorted(b,key=itemgetter(1,2,3,4,5,6,7,8,9,10,11),reverse=True)    
else:
    b=sorted(b,key=itemgetter(1,2,3,4,5,6,7,8,9,10,11,12),reverse=True) 

c=[0 for i in range(m)] 
res=0
aa=0
if not flag:
    print(-1)
else:
    for i in range(0,n):
        if aa==1:
            break
        res=res+b[i][0]
        f=True
        for j in range(1,m+1):
            c[j-1]=c[j-1]+b[i][j]
        for k in range(0,m):
            if c[k]<x:
                f=False
        if f:
            break
            aa=1
    print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
a.sort(reverse=True)
a = np.array(a)
ans = np.array([0 for i in range(m+1)])
for i in a:
    ans += i

for i in ans[1:]:
    if i < x:
        print(-1)
        exit()

for i in a:
    cnt = 0
    tmp = ans - i
    for j in tmp[1:]:
        if j >= x:
            cnt += 1
            if cnt == m:
                ans -= i

print(ans[0])

Submission status: Wrong Answer

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

a=[]

for i in range(0,n):
    aa=input().split()
    for j in range(0,m+1):
        aa[j]=int(aa[j])
    a.append(aa)

smin=100000*n
d=100000*n


for i in range(0,2**n):
    mo=0
    x2=[1 for i2 in range(0,m)]
    
    for j in range(0,n):
        if ((i>>j)&1)==1:
            mo+=a[j][0]
            for k in range(0,m):
                x2[k]+=a[j][k+1]

    if min(x2)>=x:
        if mo<smin:
            smin=mo
    

if smin==d:
    print(-1)

else:
    print(smin)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
import sys

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

C = []
A = []
ALL = []

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

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])
  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 main():
    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)
    ans = 0
    rikaido = [0]*m
    for i in c:
        ans += i[0]
        for num, val in enumerate(i[1:]):
            rikaido[num] += val
        if min(rikaido) >= x:
            break        
    if min(rikaido) < x: ans = -1
    print(ans)
if __name__ == "__main__":
    main()

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]*6
  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 i:
    if X > 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 sys
import math

n, m, x = map(int, input().split())
lis = [[0] * (m+1) for i in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(m+1):
        lis[i][j] = tmp[j]
check = [[0] * 2 for i in range(n)]
price =0
tmpp=0
algo = 0
for i in range(1,m+1):
    for j in range(n):
        check[j][0] = lis[j][i]
        check[j][1] = lis[j][0]
    check.sort(reverse=True, key=lambda x: x[0] / x[1])
    for j in range(n):
        algo += check[j][0]
        tmpp += check[j][1]
        if (algo >= x):
            price = max(price, tmpp)
            break
    tmpp = 0
    if (algo < x):
        print(-1)
        sys.exit()
    algo=0
print(price)

Submission status: Wrong Answer

Solution code:
import itertools

n,m,x=[int(i) for i in input().split(" ")]
l=[]
for i in range(n):
    l.append([int(i) for i in input().split(" ")])

l.sort()

ans=[]

for i in range(1,n+1):
    for pair in itertools.combinations(l,i):
        sumL=[0]*m
        for p in pair:
            for j in range(m):
                sumL[j]+=p[j+1]
        flag=True
        for j in range(m):
            if sumL[j]<x:
                flag=False
                break
        if flag:
            # print(pair,sumL)
            ans.append(sum([i[0] for i in pair]))

            break

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
def I(): return(list(map(int,input().split())))
def sieve(n):
	a=[1]*n
	for i in range(2,n):
	    if a[i]:
	        for j in range(i*i,n,i):
	            a[j]=0
	return a

n,m,x=I()
a=[[0]*m for i in range(n)]
c=[0]*n


for i in range(n):
	l=I()
	c[i],a[i]=l[0],l[1:]
# for i in range(m):

# idxs=list(range(n))
# idxs.sort(key=lambda i:c[i]/sum(a[i]))
maxcost=0
f=0
for i in range(m):
	idxs=list(range(n))
	idxs.sort(reverse=True,key=lambda j:a[j][i]/c[j])
	cost=0
	curr=0
	# print(idxs)
	for j in idxs:
		if curr>=x:break
		cost+=c[j]
		curr+=a[j][i]
		# print(j)
	if curr<x:
		f=1
		break
		
	maxcost=max(cost,maxcost)
if not f:
	print(maxcost)
else:
	print(-1)




# for i in range(n):

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, m, x = MAP()
bene = [[0]*(m+1) for i in range(n)]
for i in range(n):
    a = LIST()
    bene[i] = a

def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

bene = sorted(bene)
result = []
for n in range(1,len(bene)+1):
    for conb in itertools.combinations(bene, n):
        conb = list(conb)
        res = conb[0]
        for i in range(len(conb)-1):
            res = add(res, conb[i+1])
        result.append(res) 
result = sorted(result)

for i in range(len(result)):
    if result[i][1:] >= [x]*m:
        print(result[i][0])
        sys.exit()
print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import numpy as np
N, M, X = map(int, input().split())
xx = np.array([X for _ in range(M)])

C = {}
costs = []
for _ in range(N):
    c, *A = map(int, input().split())
    C[c] = A
    costs.append(c)
ans = float('inf')
for i in range(0, N+1):
    for comb in combinations(costs, i):
        tmp = 0
        x = xx.copy()
        for cost in comb:
            tmp += cost
            x -= np.array(C[cost])
        if len(x[x <= 0]) >= M:
            ans = min(ans, tmp)

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

Submission status: Wrong Answer

Solution code:
import sys
N, M, X = map(int, sys.stdin.readline().split())
CA = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
ans = 1000000000
for i in range(2 ** N):
    TMP = [0] * len(CA)
    op = [1] * N
    for j in range(N):
        if (i >> j) & 1:
            op[j] = 0
    for k in range(len(op)):
        if op[k]:
            TMP = list(map(lambda x,y: x + y, TMP, CA[k]))
    TMP_2 = [l for l in TMP[1:] if l >= X]
    if len(TMP_2) + 1 == len(TMP):
        ans = min(ans, TMP[0])
if ans == 1000000000:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m, x = map(int, input().split())
cost = []
case = [0 for _ in range(m)]
zyuku = []
for i in range(n):
    foo = list(map(int, input().split()))
    cost.append([foo[0], i])
    zyuku.append(foo[1:])
    
frag = 0
for i in range(len(zyuku[0])):
    s = 0
    for j in range(len(zyuku)):
        s += zyuku[j][i]
    if(s < x):
        frag = 1
    if(frag == 1):
        break
per = []
if(frag == 0):
    ans = 0
    sss = 0
    cost.sort(key=lambda x:x[0])
    order = []
    for i in range(n):
        order.append(cost[i][1])
    frag1 = False
    while(not(frag1)):
        case = [case[i] + zyuku[order[sss]][i] for i in range(m)]
        ans += cost[sss][0]
        frag1 = True
        for i in range(m):
            if(case[i] < x):
                frag1 = False
        if(frag1):
            break
        sss += 1
    for nu in range(len(order)):
        case1 = [case[i] - zyuku[order[nu]][i] for i in range(m)]
        frag2 = True
        for t in range(m):
            if(case1[t] < x):
                frag2 = False
        if(frag2):
            per.append(ans-cost[nu][0])
    if(len(per) == 0):
        print(ans)
    else:
        print(min(per))
else:
    print(-1)

Submission status: Wrong Answer

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

# print(A)
# print(C)

ans_money = float('inf')
# ans_algorythm = None
for i in range(2**(N-1)):
    bit = bin(i)[2::]
    # print("bit: {}".format(bit))
    tmp_money = 0
    tmp_algorythm = [0] * M
    for j, b in enumerate(bit[::-1]):
        if b == '1':
            tmp_money += C[j]
            for k, c in enumerate(A[j]):
                tmp_algorythm[k] += c
    # print("tmp_money: {}, tmp_algorythm: {}".format(tmp_money, tmp_algorythm))
    if len(list(filter(lambda x: x < X, tmp_algorythm))) == 0:
        ans_money = min(tmp_money, ans_money)
        break

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