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: Runtime Error

Solution code:
def main():
    N,M,X=(int(x) for x in input().split())
    IN=""
    result=[0]*M
    P=[0]*M
    SUM=0
    while 1:
        try:
            IN=(int(x) for x in input().split())        
        except:
            break
        SUM+=IN[0]
        for i in range(M):
            P[i]+=IN[i+1]
            if(P[i]>=X):
                result[i]=1
        if(result.count(0)==0):
            print(SUM)
            return
    print("-1")
if(__name__=='__main__'):
    main()

Submission status: Runtime Error

Solution code:
n,k= list(map(int, input().split()))
li= list(map(int, input().split()))
c=[1]
nex=1
first=0
for i in range(k):
    nex=li[nex-1]
    if nex in c:
        first=c.index(nex)
        break
    c.append(nex)
if first:
    k-=first
    k%=len(c)-first
    print(c[first+k])
else:
    print(c[-1])

Submission status: Runtime Error

Solution code:
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')
for i in range(1, M + 1):
    t_list = list(map(list, combinations(books, i)))
    for combi in t_list:
        cost, a, b, c = 0, 0, 0, 0
        for nums in combi:
            cost += nums[0]
            a += nums[1]
            b += nums[2]
            c += nums[3]
        if a >= X and b >= X and c >= X:
            min_cost = min(min_cost, cost)
if min_cost == float('inf'):
    print(-1)
else:
    print(min_cost)

Submission status: Runtime Error

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

ans = 10**9

for i in range(2**n):
    ls = [0] * m
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            ls = [l + a for l, a in zip(ls, CA[j][1:])]
            tmp += CA[j][0]
    if all(i >= x for i in ls):
        ans = min(ans, tmp)
print(ans if ans != 10**9 else -1)

Submission status: Runtime Error

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

ans = []

for i in range(2 ** n):
    jud = [0]*(m-1)
    money = 0
    for j in range(n):
        if (i >> j) & 1:
            money += ca[j][0]
            for k in range(m-1):
                jud[k] += ca[j][k]
    if min(jud) >= x:
        ans.append(money)

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

Submission status: Runtime Error

Solution code:
from itertools import product
n, m, x = map(int, input().split())
books = [[int(j) for j in input().split()] for i in range(n)]
min_cost = float('inf')
for bit in product([0, 1], repeat=n):
    cost = 0
    skill = [0] * m
    for i, b in enumerate(bit):
        if b == 1:
            cost += books[i][0]
            for j in range(m):
                skill[j] += books[i][j + 1]
    if x <= min(*skill):
        min_cost = min(min_cost, cost)
print(min_cost if min_cost != float('inf') else -1)

Submission status: Runtime Error

Solution code:
N , M ,X = map(int,input().split())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
ans = []
for i in range(2 ** N):
    rikai = [0 for _ in range(M)]
    cost = 0
    for b in range(N):
        if i  & (1 <<  b):
            for x in range(1,M + 1):
                rikai[x-1] += L[b][x] 
            cost += L[b][0]
    for x in rikai:
        if x < X: break
    else:
        ans.append(cost)

print(min(ans))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

# 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():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    A = [[int()] * (M+1) for _ in range(N)] # type: "List[int]"

    for i in range(N):
        A[i] = [int(next(tokens)) for _ in range(M+1)]
    
    # print(A)

    import numpy as np
    A = np.array(A)
    min_c = [10000000]

    def dfs(k, dep):
        if dep == N-1:
            if (k[1:]>=X).all():
                min_c[0] = min(min_c[0], k[0])
            elif (k[1:]+A[dep][1:]>=X).all():
                min_c[0] = min(min_c[0], k[0]+A[dep][0])
        else:
            dfs(k+A[dep],dep+1)
            dfs(k,dep+1)

    dfs(A[0], 1)          
    dfs(np.zeros(M+1,dtype=int), 1)
    
    if min_c[0] != 10000000:
        print(min_c[0])
    else:
        print(-1)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import log2,floor,ceil,sqrt
# import bisect
sys.setrecursionlimit(10**5)
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

def backtrack(arr,cur,ans):
    if cur == n:
        alg = [0]*n
        cost  = 0
        for i in range(len(arr)):
            if arr[i] == 1:
                cost+=c[i]
                for j in range(m):
                    alg[j] += lis[i][j]
        flag = True
        for i in range(m):
            if alg[i] < k:
                flag = False

                break
        if flag :
            ans[0] = min(ans[0],cost)
        return
    arr[cur] = 0
    backtrack(arr,cur+1,ans)
    arr[cur] = 1
    backtrack(arr,cur+1,ans)
    arr[cur] = 0

n,m,k  = Ri()
c = [0]*n
lis = []
for i in range(n):
    temp = Ri()
    c[i] = temp[0]
    lis.append(temp[1:])

arr = [0]*n
ans = [INF]
backtrack(arr,0,ans)
if ans[0] == INF:
    print(-1)
else:
    print(ans[0])

Submission status: Runtime Error

Solution code:
import numpy as np
n,m,x=map(int,input().split())
MAX=9999999999

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

c=np.array(c)
a=np.array(a)

pat=2**n
ans=MAX
for i in range(pat):
    pat_i=bin(i)[2:].zfill(3)
    ai=np.array([0 for _ in range(m)])
    ansi=0

    for j in range(len(pat_i)):
        if(pat_i[j]=='1'):
            ansi+=c[j]
            ai+=a[j]

    if(min(ai)>=x):
        ans=min(ans,ansi)

if(ans!=MAX):
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

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

minprice=[-1]
for i in range(m):
  for j in range(n):
    maxi = j
    for k in range(j,n):
      if A[maxi][i] < A[k][i]:
        maxi = k
    temp = A[maxi][i]
    A[maxi][i] = A[j][i]
    A[j][i] = temp
  x_m=0
  p_m
  for j in range(n):
    if x_m < x:
      x_m += A[j][i]
      p_m += A[j][0]
  minprice.append(p_m)
  
print(min(minprice))

Submission status: Runtime Error

Solution code:
import sys
from math import log2,floor,ceil,sqrt
# import bisect
sys.setrecursionlimit(10**4)
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

def backtrack(arr,cur,ans):
    if cur == n:
        alg = [0]*n
        cost  = 0
        for i in range(len(arr)):
            if arr[i] == 1:
                cost+=c[i]
                for j in range(m):
                    alg[j] += lis[i][j]
        flag = True
        for i in range(m):
            if alg[i] < k:
                flag = False

                break
        if flag :
            ans[0] = min(ans[0],cost)
        return
    arr[cur] = 0
    backtrack(arr,cur+1,ans)
    arr[cur] = 1
    backtrack(arr,cur+1,ans)
    arr[cur] = 0

n,m,k  = Ri()
c = [0]*n
lis = []
for i in range(n):
    temp = Ri()
    c[i] = temp[0]
    lis.append(temp[1:])

arr = [0]*n
ans = [INF]
backtrack(arr,0,ans)
if ans[0] == INF:
    print(-1)
else:
    print(ans[0])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N,M,X = map(int, input().split())
    ca = []
    res = sys.maxsize
    for _ in range(N):
        ca.append(list(map(int, input().split())))
    for i in range(2 ** N):
        tmp = [0]*M
        tmpres = 0
        for j in range(N):
            if ((i >> j) & 1):
                tca = ca[M-1-j]
                tmpres += tca[0]
                for k in range(M):
                    tmp[k] += tca[1+k]
        tassei = True
        for a in tmp:
            if a < X:
                tassei = False
                break
        if tassei:
            res = min(res,tmpres)
    if res != sys.maxsize:
        print(res)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import log2,floor,ceil,sqrt
# import bisect
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

def backtrack(arr,cur,ans):
    if cur == n:
        alg = [0]*n
        cost  = 0
        for i in range(len(arr)):
            if arr[i] == 1:
                cost+=c[i]
                for j in range(m):
                    alg[j] += lis[i][j]
        flag = True
        for i in range(m):
            if alg[i] < k:
                flag = False

                break
        if flag :
            ans[0] = min(ans[0],cost)
        return
    arr[cur] = 0
    backtrack(arr,cur+1,ans)
    arr[cur] = 1
    backtrack(arr,cur+1,ans)
    arr[cur] = 0

n,m,k  = Ri()
c = [0]*n
lis = []
for i in range(n):
    temp = Ri()
    c[i] = temp[0]
    lis.append(temp[1:])

arr = [0]*n
ans = [INF]
backtrack(arr,0,ans)
if ans[0] == INF:
    print(-1)
else:
    print(ans[0])

Submission status: Runtime Error

Solution code:
def resolve():
    N,M,X = map(int,input().split())
    CA = [list(map(int,input().split())) for i in range(N)]
    mxc = float('inf')
    for r in range(N+1):
        for cmb in itt.combinations(CA,r):
            cost = 0
            tbl = [0]*M
            for x in cmb:
                cost+=x[0]
                for i in range(M):
                    tbl[i]+= x[i+1]

            for i in tbl:
                if i < X:
                    break
            else:
                mxc = min(cost,mxc)
                
    if mxc == float('inf'):
        print(-1)
    else:
        print(mxc)



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from itertools import product
n, m, x = list(map(int, input().split()))
cl = [0] * n
al = [[]*m for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    cl[i] = tmp[0]
    al[i] = tmp[1:]


def dfs(status, book):
    for i in range(m):
        status[i] += book[i]
    return status


ans = 10**10
for bit in product([0, 1], repeat=n):
    # print(bit)
    status = [0]*n
    money = 0
    for i, b in enumerate(list(bit)):
        if b == 1:
            status = dfs(status, al[i])
            money += cl[i]
    flag = True
    for i in range(m):
        if status[i] >= x:
            continue
        else:
            flag = False
    if flag:
        ans = min(ans, money)
if ans == 10**10:
    print(-1)
    exit()
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

def main():
    N, M, X = map(int, input().split())
    C = [None] * N
    A = [None for _ in range(N)]
    for i in range(N):
        C[i], *A[i] = map(int, input().split())
    
    # print(C,A)
    ans = 10**12
    for i in range(2**N):
        tmp = [0] * N
        tmpC = 0
        for j in range(N):
            if (i >> j) & 1:
                for k in range(M):
                    tmp[k] += A[j][k]
                tmpC += C[j]
        flag = True
        for k in range(M):
            if tmp[k] < X:
                flag = False
                break
        if flag:
            ans = min(ans, tmpC)
    
    if ans == 10**12:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m, x = map(int, readline().split())
ca = [list(map(int, readline().split())) for _ in range(n)]
ans = float('inf')
for bit in product([0, 1], repeat=n):
    cnt = 0
    memo = [0] * n
    for i in range(n):
        if bit[i] == 1:
            cnt += ca[i][0]
            for j in range(m):
                memo[j] += ca[i][j + 1]
    for j in range(m):
        if memo[j] < x:
            break
    else:
        ans = min(ans, cnt)
if ans == float('inf'):
    ans = -1
print(ans)