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: Accepted

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

L = 2**N
rlt = float('inf')
sk = [0]*M

for i in range(L):
  flag = 1
  tmp = 0
  tsk = [0]*M
  lst = bin(i)[2:].zfill(N)
  for j in range(N):
    if lst[j] == '1':
      #print(i)
      tmp += CAs[j][0]
      for k in range(M):
        tsk[k] += CAs[j][k+1]
  for k in range(M):
    if tsk[k] < X:
      flag = 0
      break
  if flag == 1 and tmp < rlt:
    rlt = tmp

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

Submission status: Accepted

Solution code:
from itertools import combinations
N, M, X = map(int, input().split())
CA = [tuple(map(int, input().split())) for _ in range(N)]

ans = None
for n in range(1, N + 1):
    for cas in combinations(CA, n):
        atotals = [0] * M
        ctotal = 0
        for ca in cas:
            for i, a in enumerate(ca[1:]):
                atotals[i] += a
            ctotal += ca[0]
        if all(map(lambda atotal: atotal >= X, atotals)):
            if ans is None:
                ans = ctotal
            else:
                ans = min(ans, ctotal)
if ans is None:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:

from itertools import combinations
from copy import deepcopy
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        books.append(list(map(int, input().split())))
    books_pattern = []
    books_num = [i for i in range(n)]
    for i1 in range(1, n + 1):
        books_pattern += list(combinations(books_num, i1))
    skill_set = []

    for ebp in books_pattern:
        skill_pattern = [0] * (m + 1)
        for ebpe in ebp:
            book_e = books[ebpe]
            for i2 in range(m + 1):
                skill_pattern[i2] += book_e[i2]
        skill_set.append(skill_pattern)

    skill_set_ok = []
    for ess in skill_set:
        tess = deepcopy(ess[1:])
        tessc = [i for i in tess if i >= x]
        if len(tessc) == m:
            skill_set_ok.append(ess[0])
    if len(skill_set_ok) > 0:
        print(min(skill_set_ok))
    else:
        print(-1)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M, X = map(int, input().split())
    C = [list(map(int, input().split())) for i in range(N)]
    # print(C)
    pCOST = float("inf")
    for bit in range(1<<N):
        COST = 0
        SJ = [0]*M
        for j in range(N):
            if bit>>j & 1:
            # if bit>>(j+1) & 1:
                COST += C[j][0]
                for k in range(1,M+1):
                    SJ[k-1] += C[j][k]
        for l in range(M):
            if SJ[l] >= X:
                continue
            else:
                COST = float("inf")
                break
        pCOST = min(pCOST, COST)
    if pCOST == float('inf'):
        print(-1)
    else:
        print(pCOST)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from itertools import  product
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for _ in range(n)]
for i in range(1,m+1):
    count=0
    for j in range(n):
        count+=ca[j][i]
    if count<x:
        print(-1)
        exit()

ans=10**9



for z in product((0, 1), repeat=n):#bit全探索のくみあわせを勝手に作ってくれるので使うとよい
    count=0
    count2=[0]*m
    for i in range(n):
        if z[i]==1:
            count+=ca[i][0]
            for j in range(1,m+1):
                count2[j-1]+=ca[i][j]
    
    for i in range(m):
        if count2[i]<x:
            break
    else:
        ans=min(count,ans)
print(ans)

Submission status: Accepted

Solution code:
N,M,X =map(int,input().split())
min_money = 10**9
books =[None]*N
for i in range(N):
    books[i] = list(map(int,input().split()))

for i in range(1<<N):
    output = []
    for j in range(N):
        if ((i>>j) & 1) == 1:
            output.append(1)
        else:
            output.append(0)

    money = 0
    gakusyuu = [0]*M
    for k in range(N):
        if output[k] == 1:
            money+=books[k][0]
            for l in range(1,M+1):
                gakusyuu[l-1]+=books[k][l]

    for i in range(len(gakusyuu)):
        if gakusyuu[i] < X:
            break
    else:
        if min_money>money:
            min_money = money

if min_money == 10**9:
    print(-1)
else:
    print(min_money)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
n, m, x = map(int, input().split())

cost = np.empty(n, dtype=int)
skill_up = np.zeros((n, m), dtype=int)

for i in range(n):
    l = list(map(int, input().split()))
    cost[i] = l[0]
    skill_up[i,:] = l[1:]

flag = False
min_cost = np.sum(cost)
for i in range(1, 2 ** n):
    bidx = bin(i)[2:].rjust(n, '0')
    mask = list(map(lambda x: x == '1', list(bidx)))
    skill = np.sum(skill_up[mask], axis=0)
    if np.all(skill >= x):
        flag = True
        min_cost = min(min_cost, np.sum(cost[mask]))

if not flag:
    min_cost = -1

print(min_cost)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
# print(a)
ans=10**18
for i in range(1<<n):
  t_money=0
  t_rikai=[0]*m
  ok=True
  for j in range(n):
    if i&(1<<j): 
      t_money+=a[j][0]
      for k in range(m):
        t_rikai[k]+=a[j][k+1]
  for y,r in enumerate(t_rikai):
    if r>=x:
      pass
    else:
      ok=False
      break
  if ok:
    ans=min(t_money,ans)
  
if ans==10**18:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
num_books,m,min_understanding=list(map(int,input().split()))
info=[]
for _ in range(num_books):
    arr=list(map(int,input().split()))
    info.append(arr)
#print(info)
from itertools import combinations
l=[i for i in range(1,num_books+1)]
new=[]
for i in range(1,num_books+1):
    new.append(list(combinations(l,i)))
#print(new)
def add(l1,l2):
    faltu=[0 for i in range(len(l1))]
    #print(len(l1),len(l2),"fds")
    #print(l1,l2,"daa")
    for i in range(len(l1)):
        faltu[i]=l1[i]+l2[i]
    return faltu
def check(temp):
    #print(temp,len(temp))
    ans=[0 for i in range(m+1)]
    for i in range(len(temp)):
        ans=add(ans,info[temp[i]-1])
    for i in range(1,len(ans)):
        if ans[i]>=min_understanding:
            continue
        else:
            return 999999999
    return ans[0]
tempo=[]
for i in new:
    for j in i:
        tempo.append(check(j))
if min(tempo)==999999999:
    print(-1)
else:
    print(min(tempo))#arr[0] would be the price of that book

Submission status: Accepted

Solution code:
#int(input())
#int(x) for x in input().split()
#map(int,input().split())
def ad(l,x):
	for i in range(1,len(l)+1):
		l[i-1]+=x[i]
from itertools import combinations
n,m,X=map(int,input().split())
l=[]
for i in range(n):
	l.append([int(x) for x in input().split()])
l.sort()
comb=[i for i in range(n)]
ml=[0]*m
cost=10**9
for i in range(1,n+1):
	coco=list(combinations(comb,i))
	for j in range(len(coco)):
		ml=[0]*m
		c=0
		for k in range(len(coco[j])):
			c+=l[coco[j][k]][0]
			ad(ml,l[coco[j][k]])
			#print(ml)
			if min(ml)>=X:
				cost=min(c,cost)
				break
		if min(ml)>=X:
			cost=min(c,cost)

if cost==10**9:
	print(-1)
else:
	print(cost)

Submission status: Accepted

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

mini_cash=12*10**5+2

for alllist in list(itertools.product([0,1], repeat=n)):
    #print(alllist)
    temp_mini_cash=0
    knowledge = [0]*m
    j = 0
    for i in alllist:
        if i==1:
            for k in range(m):
                knowledge[k]+=Text[j][1+k]
                #print(Text[j][1+k])
            temp_mini_cash +=Text[j][0]
        j+=1
    #print(temp_mini_cash)
    #print(knowledge)
    if all([i >= x for i in knowledge]):
        if temp_mini_cash<mini_cash:
            mini_cash=temp_mini_cash
if mini_cash!=12*10**5+2:
    print(mini_cash)
else:print("-1")

Submission status: Accepted

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

C = []
A = []

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

C2 = []
A2 = []

for i in range(2**N):
    su = [0]*M
    sai = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(M):
                su[k] += A[j][k]
            sai += C[j]
    C2.append(sai)
    A2.append(su)

ans = 10000000000

for i in range(len(A2)):
    flag = True
    for j in A2[i]:
        if j < X:
            flag = False
    if flag:
        if ans > C2[i]:
            ans = C2[i]

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

Submission status: Accepted

Solution code:
import copy
from itertools import combinations

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

books = []

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

combi = []

for i in range(1, len(books) + 1):
    for conb in combinations(books, i):
        combi.append(list(conb))

min_result = None
for i in combi:
    result = copy.deepcopy(i[0])

    for j in i[1:]:
        for k in range(len(j)):
            result[k] += j[k]

    flag = True

    for j in result[1:]:
        if j < X:
            flag = False
            break

    if flag and (min_result is None or min_result > result[0]):
        min_result = result[0]

if min_result is None:
    print(-1)
else:
    print(min_result)

Submission status: Accepted

Solution code:
# coding: utf-8
N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
    L=list(map(int,input().split()))
    C.append(L[0])
    A.append(L[1:])

ans=-1
for i in range(2**N):
    skill=[0 for i in range(M)]
    cost=0
    flg=True
    for j in range(N):
        if i >> j &1:
            cost+=C[j]
            for k in range(M):
                skill[k]+=A[j][k]
    
    for k in range(M):
        if skill[k]<X:
            flg=False
    if flg:
        if ans==-1:
            ans=cost
        else:
            ans=min(ans,cost)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, X = map(int, input().split())
books = list()
tst = [0] * M
for _ in range(N):
    C, *A = map(int, input().split())
    books.append((C, A))
    for i, aa in enumerate(A):
        tst[i] += aa
if len([t for t in tst if t < X]) > 0:
    print("-1")
    exit()
r = None
for i in range(1, N+1):
    for j in itertools.combinations(range(len(books)), i):
        cost = 0
        tst = [0] * M
        for b in j:
            co, ms = books[b]
            cost += co
            for i, aa in enumerate(ms):
                tst[i] += aa
        if len([t for t in tst if t < X]) == 0:
            if r is None or r > cost:
                r = cost
print(r)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
A = [[] for _ in range(n)]
for i in range(n):
    A[i] = list( map(int,input().split()) )
    
flag = 0
min_charge = 10**7

for i in range(2**n):
    which = format(i, '#020b')[-n:]
    
    #print(which,end = ':')
    
    charge = 0
    skill = [0 for _ in range(m)]
    for j in range(n):
        if which[j]=='1':
            charge += A[j][0]
            for k in range(m):
                skill[k]+=A[j][k+1]
    flag_skill = 1
    for l in range(m):
        if skill[l] < x:
            flag_skill = 0
    
    
    #print(skill,end=':')
    #print(charge,end=':')    
    
    if flag_skill ==1:
        min_charge = min(min_charge,charge)
    
    #print(flag_skill)

if min_charge == 10**7:
    print(-1)
else:
    print(min_charge)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
def main():
    n, m, x = map(int, input().split())
    lst = []
    for _ in range(n):
        tmp = list(map(int, input().split()))
        lst.append(tmp)
    
    bango = [i for i in range(n)]
    k = 1
    minkingaku = float('inf')
    flag = False
    while k <= n:
        combs = combinations(bango, k)
        for comb in combs:
            
            algo = np.zeros(m)
            kingaku = 0
            for c in comb:
                algo += np.array(lst[c][1:])
                kingaku += lst[c][0]
            
            if (algo >= x).all():
                flag = True
                if kingaku <= minkingaku:
                    minkingaku = kingaku
            

        k += 1
    if flag:
        print(minkingaku)
    else:
        print('-1')
main()

Submission status: Accepted

Solution code:
import itertools

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

C = []
A = []

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

ans = -1

queue = [[0, 0, [0] * M]]
while queue:
    index, price, study_list = queue.pop(0)

    if index < N:
        queue.append([index + 1, price, study_list])

        price_2 = price + C[index]
        study_list_2 = study_list[:]
        for i in range(M):
            study_list_2[i] += A[index][i]

        queue.append([index + 1, price_2, study_list_2])
    else:
        flag = True
        for s in study_list:
            if s < X:
                flag = False
                break
        if flag:
            if ans == -1:
                ans = price
            else:
                ans = min(ans, price)
print(ans)

Submission status: Accepted

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])]

        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: Accepted

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

n, m, k = map(int, input().split())
a = []
r = []
now = []

def f(i):
    global n, k
    flag = 0

    if i + 1 == n:
        if min(now[1:]) >= k:
            r.append(now[0])
        return

    f(i + 1)

    for x in range(m + 1):
        now[x] += a[i + 1][x]

    f(i + 1)

    for x in range(m + 1):
        now[x] -= a[i + 1][x]
    

for x in range(n):
    b = [int(y) for y in input().split()]
    a.append(b)

now = a[0]
f(0)

now = [0] * (m + 1)
f(0)

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

Submission status: Accepted

Solution code:


n, m, x = [0] * 3
c = []
a = []

def format_input(filename = None):
	global n, m, x
	global c
	global a
	if filename == None:
		n, m, x = list(map(int, input().split()))
		ca = [list(map(int, input().split())) for i in range(n)]
		for i in ca:
			c.append(i[0])
			a.append(i[1:])

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 12)
		m = rng(1, 12)
		x = rng(1, 10**5)
		c = [rng(1, 10**5) for i in range(n)]
		a = [[rng(1, 10**5) for j in range(m)] for i in range(n)]
		print(n, m, x)
		[print(c[i], ' '.join(list(map(str, a[i])))) for i in range(n)]

def get_answer():
	answer = sum(c) + 1

	for k in range(2**n):
		understand = [0] * m
		price = 0
		bit = k
		i = 0
		while bit != 0:
			for j in range(m):
				understand[j] += a[i][j] * (bit & 1)
			price += c[i] * (bit & 1)
			bit >>= 1
			i += 1
		check = True
		for j in range(m):
			if understand[j] < x:
				check = False
		if check:
			answer = min(answer, price)

	if answer == sum(c) + 1:
		answer = -1

	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Accepted

Solution code:
import copy
from functools import lru_cache
n, m, x = map(int, input().split())

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

mn = float('inf')
smart = [0] * m

def good():
    global x, smart

    for kn in smart:
        if kn < x:
            return False
    
    return True

@lru_cache(maxsize=None)
def solve(idx, n, sm):
    global mn, books, smart

    if idx == n:
        if good():
            #print(' '.join(list(map(str, smart))))
            mn = min(mn, sm)
        return

    #smart1 = copy.deepcopy(smart)

    cur_books = books[idx][1]
    cost = books[idx][0]
    for i in range(len(smart)):
        smart[i] += cur_books[i]

    solve(idx + 1, n, sm + cost)

    for i in range(len(smart)):
        smart[i] -= cur_books[i]

    solve(idx + 1, n, sm)


solve(0, n, 0)

print(mn if mn != float('inf') else -1)

Submission status: Accepted

Solution code:
def resolve():
    N, M, X = map(int, input().split())
    L = []*M
    ans = 10000000000
    for i in range(N):
        L.append(tuple(map(int, input().split())))

    for i in range(2 ** N):
        s = 0
        C = [0]*M
        for j in range(N):
            if (i >> j) & 1:
                C = [a+b for (a, b) in zip(C, L[j][1:])]
                s += L[j][0]
        CC = len([c for c in C if c >= X])
        if CC == M:
            ans = min(ans, s)
    print(-1 if ans == 10000000000 else ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
C=[0]*N
A=[[0]*M for i in range(N)]


for i in range(N):
    hon = list(map(int,input().split()))
    C[i]=hon[0]
    for j in range(M):
        A[i][j] = hon[j+1]
rikaido=[0]*M
ans = 20*(10**5)
for i in range(2**N):
    pattern=[0]*N
    temp = 0
    rikaido=[0]*M
    for j in range(N):
        if (i >> j & 1):
            for k in range(M):
                pattern[j] =1
                rikaido[k]+=A[j][k]
            temp+=C[j]
    flag = 0
    for i in range(M):
        if rikaido[i] < X:
            flag = 1
    if flag ==0 and temp < ans:
        ans = temp

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

Submission status: Accepted

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


C =[]
A = {}

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

bestscore = 99999999999
def rec(n, score, money):
    global bestscore
    if n==N: return
    s = copy.deepcopy(score)
    rec(n+1, s, money)

    money += C[n]
    for i in range(M):
        score[i] += A[n][i]
    

    for i in range(M):
        if score[i] < X:
            s = copy.deepcopy(score)
            rec(n+1, s, money)
            return
    bestscore = min(bestscore, money)

score = [0 for i in range(M)]

rec(0, score, 0)
if bestscore == 99999999999:
    print(-1)
else:
    print(bestscore)

Submission status: Accepted

Solution code:
n, m , x = map(int, input().split())
c, a = [], []
for _ in [0]*n:
    temp = list(map(int, input().split()))
    c.append(temp[0])
    a.append(temp[1:])

sign = (1, 0)

ans = float("inf")
import numpy as np
from itertools import product
for i in product(sign, repeat = n):
    temp = np.zeros(m)
    cc = 0
    for j in range(n):
        tt = a[j]
        if i[j] == 1:
            temp += tt
        cc += c[j] * i[j]

    if np.all(temp >= x):
        ans = min(ans, cc)

print(ans if ans != float("inf") else -1)

Submission status: Accepted

Solution code:
n,m,x=list(map(int, input().split()))
ca=[]
for i in range (n):
    ca.append(list(map(int, input().split())))
u=[0]*m
for j in range (m):
    for i in range (n):
        u[j]+=ca[i][j+1]
det=1
for y in range (m):
    if u[y]<x:
        det=0
if det==0:
    print(-1)
else:
    cost=1300000
    for z in range(2**n):
        bi=[0]*n
        for p in range(n):
            if z>=2**(n-1-p):
                bi[p]=1
                z=z-2**(n-1-p)
        v=[0]*m
        for i in range(n):
            if bi[i]==1:
                for j in range(m): 
                    v[j]+=ca[i][j+1]
        de=1
        for y in range (m):
            if v[y]<x:
                de=0
        if de==1:
            cc=0
            for q in range (n):
                cc+=ca[q][0]*bi[q]
            if cc<cost:
                cost=cc
    print(cost)

Submission status: Accepted

Solution code:
import numpy as np
N, M, X  = map(int, input().split())
A = []
for i in range(N):
  A.append(list(map(int, input().split())))
A = np.array(A)
bit_base = 2#bit_base^nの全探査になる. 

def Base_10_to_n(X, n):#10進数をbit_base進数に変換
  X_dumy = X
  out = ''
  while X_dumy>0:
    out = str(X_dumy%n)+out
    X_dumy = int(X_dumy/n)
  return out
Inf = 10**9
def main():
  ans = Inf
  for i in range(bit_base**N):
    s = Base_10_to_n(i, bit_base)
    s = s.zfill(N)
    p_alg = np.zeros(M+1)
    for num, j in enumerate(s):
      if j == '1':
        p_alg += A[num]
    if all(p_alg[1:] >= X):
      ans = min(ans, p_alg[0])
  if ans == Inf:
    print(-1)
  else:
    print(int(ans))
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys

t = [int(s) for s in stdin.readline().rstrip().split()]
n = t[0]
m = t[1]
x = t[2]

data = []
for el in range(n):
    tmp = [int(s) for s in stdin.readline().rstrip().split()]
    skills = []
    count = 0
    for el2 in tmp:
        if count > 0:
            skills.append(el2)
        count += 1
    data.append({'price': tmp[0], 'skills': skills})

num = 0
priceSum = sys.maxsize
while True:
    status = [int(s) for s in'0'*m]
    price = 0
    para = [int(s) for s in str(format(num, 'b'))]
    pp = [int(s) for s in(n - len(para)) * '0']
    pp.extend(para)

    tim = 0
    for el in pp:
        if (el == 1):
            price += data[tim]['price']
            status = list(map(lambda x, y: x+y, status, data[tim]['skills']))
        tim += 1
    else:
        for el in status:
            if (el < x):
                break
        else:
            if (priceSum > price):
                priceSum = price
    if all(pp):
        break
    num += 1
if priceSum == sys.maxsize:
    print(-1)
else:
    print(priceSum)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
d = {}
for i in range(n):
  c = list(map(int, input().split()))
  d[i] = c
ans_ = 1000000000
for i in range(2**n):
  f = 0
  ans = 0
  a = format(i,'b')
  a = "{:0>12}".format(a)
  b = a[12-n:]
  e = [0]*m
  for num,j in enumerate(b):
    if j == "1":
      c = d[num]
      for num_,k in enumerate(c):
        if num_ == 0:
          ans += k
        else:
          e[num_-1] += k
  for j in e:
    if j < x:
      f = 1
      break
  if f == 0:
    ans_ = min(ans_,ans)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(n)]
C = [CA[i][0] for i in range(n)]
A = [CA[i][1:] for i in range(n)]
MC = []
for s in range(1 << n):
    X = [0 for j in range(m)]
    c = 0
    for i in range(n):
        if (s >> i) & 1 == 1:
            for j in range(m):
                X[j] += A[i][j]
            c += C[i]
    if all([X[j] >= x for j in range(m)]):
        MC.append(c)
if MC == []:
    print(-1)
else:
    print(min(MC))

Submission status: Accepted

Solution code:
import itertools

n,m,x = map(int,input().split())
C, A = [], []
for i in range(n):
    ca = list(map(int, input().split()))
    C.append(ca[0])
    A.append(ca[1:])

min_price = 10**9
for k in range(n):
    for comb in itertools.combinations(range(n), k+1):
        sums = [0] * m
        price = 0
        for c in comb:
            price += C[c]
            for i in range(m):
                sums[i] += A[c][i]

#         print(comb)
#         print(sums)
#         print(min_price)
        if sum([y >= x for y in sums]) == m:
            min_price = min(min_price, price)

if min_price == 10**9:
    print('-1')
else:
    print(min_price)

Submission status: Accepted

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


# 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 = list(map(int, input().split()))

    book_cost  = []
    book_skill = []
    for i in range(N):
        l = list(map(int, input().split()))
        book_cost.append(l[0])
        book_skill.append(l[1:])

    ans = -1

    for i in range(2**N):
        skill = [0] * M
        cost = 0
        for j in range(N):
            if ((i>>j) & 1):
                cost += book_cost[j]
                for k in range(M):
                    skill[k] += book_skill[j][k]
        if all(s>=X for s in skill):
            if ans<0:
                ans = cost
            else:
                ans = min(ans, cost)
        #print(cost, skill)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,m,x,l):
    cost = 2**31-1
    f = False
    for i in range(2**n):
        isOK,val = getcost(i,x,l,m)
        if isOK : 
            f = True
            cost = min(cost, val)
    return cost if f else -1
        
def getcost(p,x,l,m):
    flag = 1
    cost = 0
    res = [0]*m
    for i in range(len(l)):
        if (p >> i) & 1:
            cost += l[i][0]
            for j in range(len(res)):
                res[j] += l[i][j+1]
    for i in res:
        if i < x:flag = 0
    return [flag, cost if flag==1 else -1]

n,m,x = mi()
l = mix(n)
print(main(n,m,x,l))

Submission status: Accepted

Solution code:
n,m,x = [int(i) for i in input().split()]
il = []
for _ in range(n):
  il.append([int(i) for i in input().split()])
  
c_min = 10**10
ok = False
  
for i in range(2**n):
  s = bin(i)[2:].zfill(n)
  sum_a = [0] * (m+1)
  for j in range(n):
    if s[j] == '1':
      l = il[j]
      for k in range(m+1):
        sum_a[k] += l[k]
  if min(sum_a[1:]) >= x:
    ok = True
    c_min = min(c_min, sum_a[0])
      
if ok:
  print(c_min)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, m, x = i_map()
    num_list = i_row_list(n)

    money = INF

    for bit in list(product([0,1], repeat=n)):
        tmp_money = 0
        alg_list = [0] * m
        for i in range(n):
            if bit[i] == 1:
                tmp_money += num_list[i][0]
                for j in range(m):
                    alg_list[j] += num_list[i][j+1]
        for i in range(m):
            if alg_list[i] < x:
                tmp_money = INF
                break
        money = min(money, tmp_money)

    print(money if money != INF else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
lst=[0]*N
for i in range(N):
  lst[i]=list(map(int,input().split()))
x=-1
def ad(l1,l2):
  n=len(l1)
  return [l1[i]+l2[i] for i in range(n)]
for i in range(2**N):
  l0=[0]*(M+1)
  for j in range(N):
    if (i//(2**j))%2:
      l0=ad(l0,lst[j])
  if sum([j>=X for j in l0[1:]])==M:
    if l0[0]<=x or x==-1:
      x=l0[0]
print(x)

Submission status: Accepted

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

s=[list(map(int, input().split())) for _ in range(n)]
ans=10**9
for i in range(2 ** n):
    cou=0
    a=[0]*(m+1)
    b=bin(i)[2:]
    if len(b)<n:
        b=str("0"*(n-len(b)))+b
    for j in range(len(b)):
        cou=0

        if b[j]=="1":
            for k in range(m+1):
                a[k]+=s[j][k]
        # print(a,cou)
        for l in range(m):
            # print(a[l+1],x)
            if a[l+1]>=x:
                cou+=1
        # print(cou)
        if cou==m:
            ans=min(ans,a[0])
if ans==10**9:
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = []
A = []
for i in range(n):
    ls = input().split()
    C.append(int(ls[0]))
    A.append(list(map(int, ls[1:])))

flag = False
min_c = float('inf')
for i in range(2 ** n):
    min_ls = [0] * n
    tmp_c = 0
    for j in range(n):
        if i >> j & 1:
            min_ls = [a+b for a, b in zip(min_ls, A[j])]
            tmp_c += C[j]       
    if min(min_ls) >= x:        
        flag = True
        min_c = min(min_c, tmp_c)        

if flag:
    print(min_c)
else:
    print('-1')