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.

Submission attempts (in order):

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


maxi=[0 for i in range(m)]
for i in range(n):
    for j in range(m):
        maxi[j]+=a[i][j+1]
for i in range(m):
    if maxi[i]<x:
        print(-1)
        exit()

mini=100000000

for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)& 1):
            d.append(j)
    print(d)
    b=[0 for j in range(m)]
    
    c=0
    
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

print(mini)

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


for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)and 1):
            d.append(j)
    b=[0 for k in range(m)]
    
    c=0
    
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

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



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


for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)and 1):
            d.append(j)
    b=[0 for k in range(m)]
    
    c=0
    
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

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




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

maxi=[0 for i in range(m)]
for i in range(n):
    for j in range(m):
        maxi[j]+=a[i][j+1]
for i in range(m):
    if maxi[i]<x:
        print(-1)
        exit()

mini=100000000

for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)and 1):
            d.append(j)
    b=[0 for j in range(m)]
    
    c=0
    
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

print(mini)


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


maxi=[0 for i in range(m)]
for i in range(n):
    for j in range(m):
        maxi[j]+=a[i][j+1]
for i in range(m):
    if maxi[i]<x:
        print(-1)
        exit()

mini=100000000

for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)& 1):
            d.append(j)
    b=[0 for j in range(m)]
    
    c=0
    
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

print(mini)


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted