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: Time Limit Exceeded

Solution code:
def main():
    N,M,X=map(int, input().split())
    A=[list(map(int, input().split())) for _ in range(N)]
    ans=10**10**10
    for i in range(2**N):
        b=i+2**N
        c=0
        l=[0]*M
        ok=True
        for j in range(N):
            if b>>j&1 == 1:
                c+=A[j][0]
                for k in range(M):
                    l[k]+=A[j][k+1]
        for x in l:
            if x < X: ok = False 
        if ok:
            ans = min(ans, c)
    if ans==10**5*N: print('-1')
    else: print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m, x = map(int, input().split())
L = list(list(map(int, input().split())) for _ in range(n))
ans = float('inf')
p = []
for i in range(1, n + 1):
    for j in itertools.permutations(L, i):
        p.append(list(j))

for k in p:
    s = [0] * (m + 1)
    for l in range(len(k)):
        for t in range(m + 1):
            s[t] += k[l][t]
            
    sum_price = 0
    for i in range(1, m + 1):
        if s[i] < x:
            sum_price = float('inf')
            break
        sum_price = s[0]
    if sum_price < ans:
        ans = sum_price

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import itertools

n, m, x = [int(x) for x in stdin.readline().rstrip().split()]
c = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
mi = -1

for i in itertools.permutations(c, n):
    cnt = [0]*m
    mon = 0
    for j in i:
        cnt = [cnt[k]+j[k+1] for k in range(len(cnt))]
        mon += j[0]
        if sum(1 for k in cnt if k >= x) == m:
            if mi > mon or mi == -1:
                mi = mon
            break

print(mi)

Submission status: Time Limit Exceeded

Solution code:
n,m,x=map(int,input().split())
C=list()
A=list()
for i in range(n):
    c=list(map(int,input().split()))
    C.append(c[0])
    A.append(c[1:m+1])
L=[0]*m
for i in range(n):
    for j in range(m):
        L[j]+=A[i][j]
if min(L)<x:
    print(-1)
else:
    import itertools
    v=list(itertools.permutations([i for i in range(n)]))
    l=[0]*len(v)
    for i in range(len(v)):
        z=v[i]
        r=[0]*m
        for j in range(n):
            l[i]+=C[z[j]]
            for k in range(m):
                r[k]+=A[z[j]][k]
            if min(r)>=x:
                break
    print(min(l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

data_a = np.sum(data, axis=0)
#print(data_all - data[1])
data_all_zero = []
data_all = []
data_nolma = []
data_nolma.append(0)
for i in range(M + 1):
    data_all_zero.append(data_a[i])

data_all.append(data_all_zero)
#print("data_all:", data_all)

for i in range(M):
    data_nolma.append(X)

#print("data_nol:", data_nolma)





for i in range(N):
    data_all_len = len(data_all)
    for j in range(N):
        for k in range(len(data_all)):
            #print("data[j]:", data[j])
            #print("len:", len(data_all))
            data_tmp = [x - y for (x,y) in zip(data_all[k], data[j])]
            #print("data_tmp:", data_tmp)
            data_tmp_nol = [x - y for (x,y) in zip(data_tmp, data_nolma)]
            #print("data_tmp_nol:", data_tmp_nol)
            if(min(data_tmp_nol) >= 0):
                data_all.append(data_tmp)
    if(len(data_all) == data_all_len):
        break


#print(data_all)
data_all.sort()

flag = 0
for i in range(1, len(data_all[0])):
    if(data_all[0][i] < X):
        print(-1)
        flag = 1
        break
if(flag == 0):
    print(data_all[0][0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

data_a = np.sum(data, axis=0)
#print(data_all - data[1])
data_all_zero = []
data_all = []
data_nolma = []
data_nolma.append(0)
for i in range(M + 1):
    data_all_zero.append(data_a[i])

data_all.append(data_all_zero)
#print("data_all:", data_all)

for i in range(M):
    data_nolma.append(X)

#print("data_nol:", data_nolma)





for i in range(N):
    for j in range(N):
        for k in range(len(data_all)):
            #print("data[j]:", data[j])
            #print("len:", len(data_all))
            data_tmp = [x - y for (x,y) in zip(data_all[k], data[j])]
            #print("data_tmp:", data_tmp)
            data_tmp_nol = [x - y for (x,y) in zip(data_tmp, data_nolma)]
            #print("data_tmp_nol:", data_tmp_nol)
            if(min(data_tmp_nol) >= 0):
                data_all.append(data_tmp)


#print(data_all)
data_all.sort()

flag = 0
for i in range(1, len(data_all[0])):
    if(data_all[0][i] < X):
        print(-1)
        flag = 1
        break
if(flag == 0):
    print(data_all[0][0])

Submission status: Time Limit Exceeded

Solution code:
n,m,x = map(int, input().split())
import numpy as np
C = []
A = np.array([[0]*m]*n)
for i in range(n):
    l = list(map(int, input().split()))
    C.append(l[0])
    A[i] += np.array(l[1:])
D = sum(A[j] for j in range(n))
ans=[sum(C)]
L=set(range(n))

def f(L, D, cost):
    global x, A
    for i in L:
        next_D = D-A[i]
        if min(next_D) >= x:
            ans.append(cost-C[i])
            next_L = L^{i}
            f(next_L, next_D, cost-C[i])
f(L, D, sum(C))

if min(D) < x:
    print(-1)
else:
    print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

    xx = list(itertools.permutations(nn))

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

        for _ in ii:
            cost = ca[_][0]
            chk = 0
            for i in range(m):
                a[i] += ca[_][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)

 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

ans = 10 ** 6
w = [0] * m
for i in a2:
    w = [0] * m
    w_ans = 0
    for j in i:
        w = [x + y for x, y in zip(w, j[1:])]
        w_ans += j[0]

        if all([i >= x for i in w]):
            ans = min(ans, w_ans)
            break

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, m, x = [int(i) for i in input().split(' ')]
c_s = []
a_s = []

for i in range(n):
  buf = [int(i) for i in input().split(' ')]
  c_s.extend(buf[:1])
  a_s.append(buf[1:])

c_s = np.array(c_s)
a_s = np.array(a_s)


min_flag = np.array([1]*n)
min_money = 999999999

def f(flag):
  global min_money
  global min_flag
  if np.dot(flag, a_s).min() < x:
    return
  
  if np.dot(flag, c_s.T) < min_money:
    min_money = np.dot(flag, c_s.T)
    min_flag = flag
  
  for i in range(len(flag)):
    if flag[i] == 1:
      flag[i] = 0
      f(flag)
      flag[i] = 1

f([1]*n)
if min_money == 999999999:
  print('-1')
else:
  print(min_money)

Submission status: Time Limit Exceeded

Solution code:
n,m,x = map(int,input().split())
a = [0]*n
for i in range(n):
    a[i] = list(map(int,input().split()))
    
import itertools
data = list(range(n))
r = n
cc = list(itertools.permutations(data, r))

count = 0
ans = 10**7
for s in cc:
    count = 0
    sw = [0]*m
    for j in range(len(s)):
        
        for i in range(m):
            sw[i] += a[s[j]][i+1]
        count += a[s[j]][0]
        if count >= ans:
            break
        q = 1
        for k in range(m):
            if sw[k] < x:
                q = 0
                break
        if q == 1:
            ans = min(ans,count)
            break
if ans == 10**7:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools #import *
n, m, x = [int(i) for i in input().split()]


ca = [list(map(int,input().split())) for _ in range(n)]
#for j in range (n):
#    sum = 0
#    for k in range(m):
#        sum += ca[j][k+1]
#    ca[j].append(sum)

#ca =sorted(ca, key=lambda x:x[m+1], reverse = True)
#print(ca)
lst = [0]*n
for i in range(n):
    lst[i] = i

#print(lst)
#list = list(combinations_with_replacement(lst,n))
list = list(itertools.permutations(lst))
#print(list)

yasune = 10000000000

for l in list:
    budget = 0
    und=[0]*m
    for ll in l:
        #print(und)
        insuff = 0
        budget += ca[ll][0]
        for j in range(m):
            und[j] += ca[ll][j+1]
            if(und[j] < x):
                insuff = 1
        if (insuff == 0):
            yasune=min(yasune, budget)
            #print(yasune)
            break

if (yasune == 10000000000):
    print(-1)
else:
    print(yasune)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


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

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)


    cost = 0
    status = [0]*M
    minValues = [sys.maxsize]*M
    for n in range(N):
        cost += l[n][0]
        for m in range(M):
            if l[n][m + 1] < minValues[m]:
                minValues[m] = l[n][m + 1]
            status[m] += l[n][m + 1]
    
    for i in range(len(status)):
        if status[i] < X:
            print(-1)
            return
        if status[i] - minValues[i] < X:
            print(cost)
            return 

    
    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            if min_cost < cost:
                break
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

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

l=[]

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

ans=[]  
arr=np.array(l)
arr_ans=np.array([0]*(m+1))

#print(arr)
#print(arr_ans)

for l in itertools.permutations(range(n)):
  arr_ans=np.array([0]*(m+1))
  for i in l:
    arr_ans=arr_ans+arr[i]
    if np.all(arr_ans[1:]>=x):
      ans.append(arr_ans[0])
      break

if ans==[]:
  ans.append(-1)
print(min(ans))

Submission status: Time Limit Exceeded

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


# 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():
    # Failed to predict input format
    N, M, X = [int(x) for x in input().split()]
    C = []
    A = []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        C.append(tmp[0])
        A.append(tmp[1:])
    CA = [[C[i], v] for i, v in enumerate(A)]
    l = list(itertools.permutations(CA, N))
    anss = [100100100] * len(l)
    for i, v in enumerate(l):
        arr = [0] * M
        s = 0
        for j in v:
            arr = python_list_add(arr, j[1])
            s += j[0]
            if all([x >= X for x in arr]):
                anss[i] = s
                break
    ans = min(anss)
    if ans == 100100100:
        print(-1)
        return
    print(ans)
    return


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


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

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)

    cost = 0
    status = [0]*M
    for n in range(N):
        cost += l[n][0]
        for m in range(M):
            status[m] += l[n][m + 1]
    
    isJust = True
    for v in status:
        if v < X:
            print(-1)
            return
        if v != X:
            isJust = False
    if isJust:
        print(cost)
        return 


    
    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            if min_cost < cost:
                break
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import itertools
import math

    
def my_generator(C):
    for v in itertools.permutations(C):
        yield v


def check(C):
    A = [0 for i in range(M+1)]
    for i in range(N):
        A = [a + b for a, b in zip(A, C[i])]
        b = [i for i in range(M+1) if A[i] < X]
        if len(b) == 0:
            return A[0]
    else:
        print(-1)
        exit()

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

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

genlst = my_generator(C)
lenn = math.factorial(N)
m = 0
for i in range(lenn):
    C = next(genlst)

    if i == 0:
        m = check(C)
    else:
        m = min(m, check(C))
print(m)

Submission status: Time Limit Exceeded

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


# 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():
    # Failed to predict input format
    N, M, X = [int(x) for x in input().split()]
    C = []
    A = []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        C.append(tmp[0])
        A.append(tmp[1:])
    CA = [[C[i], v] for i, v in enumerate(A)]
    l = list(itertools.permutations(CA, N))
    anss = [100100100] * len(l)
    for i, v in enumerate(l):
        arr = [0] * M
        s = 0
        for j in v:
            arr = python_list_add(arr, j[1])
            s += j[0]
            if all([x >= X for x in arr]):
                anss[i] = s
                break
    ans = min(anss)
    if ans == 100100100:
        print(-1)
        return
    print(ans)
    return


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





    
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys; sys.setrecursionlimit(2147483647)
input = sys.stdin.readline
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())

from itertools import permutations
import numpy as np
def create_gen(string):
    for char in string: yield char
def main():
    N, M, X = MI()
    C = []; A = []; P = ''
    for i in range(N):
        tmp = LI()
        C.append(tmp[0]); A.append(tmp[1:]); P += str(i)
    origin_list = list(create_gen(P))
    l = set()
    for i, _ in enumerate(origin_list, 1):
        for j in permutations(origin_list, r=i):
            l.add(tuple(set(j)))
    c = {sum([C[int(j)] for j in i]):i for i in l}
    for cost, i in sorted(c.items(), key=itemgetter(0)):
        r = np.zeros(M)
        for j in i: r += np.array(A[int(j)])
        if sum(r<X) == 0: print(cost); sys.exit()
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! env/bin/local python3
# -*- coding:utf-8 -*-

# -- submit ----

import itertools
import numpy as np

# --- fetch input ---
inputs: list = []
while True:
    try:
        inputs.append(input().strip('\n'))
    except EOFError:
        break

# --- write code below ---
results = np.inf
n, m, x = map(int, inputs[0].split())
fee = {}
books = []

for j, i in enumerate(inputs[1:]):
    temp = list(map(int, i.split()))
    fee[j] = temp[0]
    books.append(temp[1:])

books = np.array(books)

p = itertools.permutations(range(n), n)
for i in p:
    temp = np.zeros(m)
    total_fee = 0
    for j in i:

        temp += books[j, :]
        total_fee += fee[j]

        if np.all(temp >= x):

            if results > total_fee:
                results = total_fee

print(results if np.isfinite(results) else -1)

Submission status: Time Limit Exceeded

Solution code:

import itertools

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

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

xx = list(itertools.permutations(nn))


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

    for _ in ii:
        cost = ca[_][0]
        chk = 0
        for i in range(m):
            a[i] += ca[_][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: Time Limit Exceeded

Solution code:
def minculc(C,A, Ml, X):
    ret = -1
    reti = list()
    for l in Ml:
        a = 0
        c = 0
        for i in range(len(l)):
            a += A[i] * l[i]
            c += C[i] * l[i]
        if a >= X:
            reti.append(l)
    return reti


def makelist(N, l):
    if N == 0:
        return [l]
    else:
        l1 = l.copy()
        l2 = l.copy()
        l1.append(0)
        l2.append(1)
        ret = makelist(N-1,l1)
        ret2 = makelist(N-1, l2)
        ret = ret.copy()
        ret.extend(ret2)
        return ret

N,M,X = map(int, input().split())
C = list()
A = list()
for i in range(N):
    tmp_ = list(map(int,input().split()))
    C.append(tmp_[0])
    A.append(tmp_[1:])
l = list()
Ml = makelist(N,l)
lcost = list()
for i in range(M):
    a = list()
    for j in range(N):
        a.append(A[j][i])
    ret_ = minculc(C,a,Ml,X)
    lcost.append(ret_)

lcost.sort(key=lambda x: len(x))
retlist = list()
for i in range(len(lcost[0])):
    for j in range(len(lcost)):
        if lcost[0][i] not in lcost[j]:
            break
        if j == len(lcost)-1:
            retlist.append(lcost[0][i])
ret = -1
if len(retlist) > 0:
    for r in retlist:
        c = 0
        for i in range(len(r)):
            c += C[i] * r[i]
        if ret == -1 or c < ret:
            ret = c
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def add_arr(a, acc):
    res = {'c': a['c'] + acc['c'], 'a': [0]*len(a['a'])}
    for i in range(len(a['a'])):
        res['a'][i] = a['a'][i] + acc['a'][i]
    return res

def understood(x, acc):
    return all([a >= x for a in acc['a']])

res = 12 * 10**5 + 1
def dfs(n, m, x, l, acc):
    global res
    if understood(x, acc):
        if acc['c'] < res:
            res = acc['c']
        return

    elif len(l) == 0:
        return

    else:
        for i in range(len(l)):
            solve(n, m, x, l[0:i] + l[i+1:len(l)], add_arr(l[i], acc))

def solve(n, m, x, l, acc):
    dfs(n, m, x, l, acc)
    return res if res < 12 * 10**5 + 1 else -1

if __name__ == '__main__':
    n, m, x = [int(arg) for arg in input().split()]
    l = []
    for _ in range(n):
        c, *a = [int(arg) for arg in input().split()]
        l.append({'c': c, 'a': a})
    print(solve(n, m, x, l, {'c': 0, 'a': [0]*m}))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


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

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)

    status = [0]*M
    for n in range(N):
        for m in range(M):
            status[m] += l[n][m + 1]
    for v in status:
        if v < X:
            print(-1)
            return
    
    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            if min_cost < cost:
                break
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


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

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)

    status = [0]*M
    for n in range(N):
        for m in range(M):
            status[m] += l[n][m + 1]
    for v in status:
        if v < X:
            print(-1)
            return
    
    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            if min_cost < cost:
                break
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import itertools
import math


def my_generator(C):
    for v in itertools.permutations(C):
        yield v

def python_list_add(A, C):
    return [a + b for a, b in zip(A, C)]

def check(A, C):
    m = 0
    for i in range(N):
        m += C[i][0]
        A = python_list_add(A, C[i])
        # print("A", A)
        b = [i for i in range(M+1) if A[i] < X]
        # print("b", b)
        if len(b) == 0:
            return m
    else:
        print(-1)
        exit()

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

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

genlst = my_generator(C)
lenn = math.factorial(N)
m = ["" for i in range(lenn)]
for i in range(lenn):
    C = next(genlst)
    A = [0 for i in range(M+1)]
    m[i] = check(A, C)
print(min(m))

Submission status: Time Limit Exceeded

Solution code:
## C
import itertools
N, M, X = map(int, input().split())
val = [list( map( int,input().split() ) ) for x in range(N)]
val = sorted(val, reverse=False, key=lambda x: x[0])
val = list(itertools.permutations(val))
rt = []
for i in val:
    tmp = [0] * (N + 1)
    for j in range(N):
        tmp = [x + y for (x,y) in zip(tmp, i[j])]
        if len([z for z in tmp[1:] if z < X]) == 0:
            rt.append(tmp[0])
            break
    else:
        continue
print(min(rt) if len(rt) > 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


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

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)

    status = [0]*M
    for n in range(N):
        for m in range(M):
            status[m] += l[n][m + 1]
    for v in status:
        if v < X:
            print(-1)
            return
    
    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

n,m,x=map(int,input().split())
ca=np.array([np.array(list(map(int,input().split()))) for i in range(n)])
l=[i for i in range(n)]
ans=10**6
for i in itertools.permutations(l):
    temp=np.zeros(m+1)
    for j in i:
        temp+=ca[j]
        if np.all(temp[1:]>=x):
            ans=min(ans,temp[0])
print(int(ans) if ans!=10**6 else '-1')