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())
a=[]
b=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

for i in range(N):
    a.append(input().split())

check=0
ans=-1
for i in range(1,pow(2,N)):
    b=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    check=0
    for j in range(N):
        if 0x01 & (i >> j):
            for n in range(M+1):
                b[n] = b[n] + int(a[j][n])
    for k in range(1,M+1):
        if b[k] < X:
            check=1
    if check==0:
        if ans == -1 or ans > b[0]:
            ans = b[0]
print(ans)

Submission status: Accepted

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

def main():
    n,m,x=map(int,input().split())
    C=[]
    A=[]
    for _ in range(n):
        c,*a=map(int,input().split())
        C.append(c)
        A.append(a)
    ans=float('inf')
    for i in range(1<<n):
        S=[0]*m
        tmp=0
        for j in range(n):
            if (i>>j)&1==0:
                continue
            tmp+=C[j]
            B=A[j]
            for k,b in enumerate(B):
                S[k]+=b
        if min(S)>=x:
            ans=min(ans,tmp)
    print(-1 if ans==float('inf') else ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c,a = [],[]
for _ in range(n):
    l = list(map(int,input().split()))
    c.append(l[0])
    a.append(l[1:])
ans = float("inf")
for i in range(2**n):
    e = [0 for _ in range(m)]
    okane = 0
    for j in range(n):
        if (i >> j) & 1:
            katta = a[j]
            okane += c[j]
            for k in range(m):
                e[k] += katta[k]
    f = min(e)
    if f >= x:
        ans = min(ans,okane)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
A=[]
for i in range(N):
    A.append(list(map(int, input().split())))
    
pr=10**9
for s in range(2**N):
    x_m = [0]*13
    for i in range(N):
        b = (s >> i) & 1
        if b == 1:
            for j in range(M+1):
                x_m[j] += A[i][j]
 
    xOk = True
    for j in range(1,M+1):
        if x_m[j] < X:
            xOk = False
    
    if xOk == True:
        pr = min(pr, x_m[0])
 
if pr<10**9:
    print(pr)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
N,M,X=map(int,input().split())
C=np.zeros(N,dtype=int)
A=np.zeros([N,M],dtype=int)
for i in range(N):
    T=list(map(int,input().split()))
    C[i]=T[0]
    for j in range(M):
        A[i,j]=T[j+1]
a=np.zeros(N,dtype=int)
ans=-1
while a.all()!=1:
  if ((a@A)>=X).all():
    if ans==-1:
        ans=a@(C.T)
    elif a@(C.T)<ans:
        ans=a@(C.T)
  for i in range(N):
    if a[N-i-1]==0:
      a[N-i-1]=1
      break
    else:
      a[N-i-1]=0

if ((a@A)>=X).all():
  if ans==-1:
      ans=a@(C.T)
  elif a@(C.T)<ans:
      ans=a@(C.T)

print(ans)

Submission status: Accepted

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

res = 10 ** 9
for i in range(2 ** N):
    c = 0
    s = [0 for _ in range(M)]
    for j in range(N):
        if i >> j & 1:
            c += C[j]
            for k in range(M):
                s[k] += L[j][k]
    f = 1
    for j in range(M):
        if s[j] < X:
            f = 0
            break
    if f:
        res = min(res, c)

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

Submission status: Accepted

Solution code:
import sys
n,m,x= map(int, sys.stdin.readline().rstrip("\n").split())
lines = [ [int(s) for s in line.split()] for line in sys.stdin ]

books = {}
num = 0
for a in range(2):
    for b in range(2):
        for c in range(2):
            for d in range(2):
                for e in range(2):
                    for f in range(2):
                        for g in range(2):
                            for h in range(2):
                                for i in range(2):
                                    for j in range(2):
                                        for k in range(2):
                                            for l in range(2):
                                                books[num] = [a,b,c,d,e,f,g,h,i,j,k,l]
                                                num += 1
price = -1
skill = {}
for i in range(2**12-1):
    price_ = 0
    for j in range (m):
        skill[j] = 0
    for j in range(n):
        if books[i+1][j] == 1:
            price_  += lines[j][0]
            for k in range(m):
                skill[k] = skill[k] + lines[j][k+1]
        for k in range(m):
            if skill[k] < x:
                break
        else:
            if price == -1:
                price = price_
            else:
                price = min(price, price_)
print(price)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
N, M, X = map(int, input().split())

row_list = []
C_list = []
for _ in range(N):
  row = list(map(int, input().split()))
  row = np.array(row)
  C_list.append(row[0])
  row_list.append(row[1:])

  
def check(subset, C_list, row_list, X):
  if len(subset) == 0:
    return 0, False
  
  cost_list = [C_list[ind] for ind in subset]
  cost = sum(cost_list)
  
  skill_arr = np.zeros(M)
  for ind in subset:
    skill_arr += row_list[ind]
    
  judge = np.min(skill_arr) >= X
    
  return cost, judge

output = np.inf
for j in range(N+1):
  for subset in combinations(range(N), j):
    cost, judge = check(subset, C_list, row_list, X)
    
    if judge and cost < output:
      output = cost

if output == np.inf:
  output = -1
  
print(output)

Submission status: Accepted

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

A = [[] for _ in range(n)]
C = [0] * n

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

INF = 10 ** 9
ans = INF

for s in range(1<<n):
    smart = [0] * m
    cost_sum = 0
    for i in range(n):
        if (s >> i) % 2 == 0: continue
        cost_sum += C[i]
        for j in range(m):
            smart[j] += A[i][j]

    ok = True
    for i in range(m):
        if x > smart[i]:
            ok = False
    
    if ok:
        ans = min(ans, cost_sum)

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

Submission status: Accepted

Solution code:
import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1


def money(arr):
	ans = 0
	for i in range(len(arr)):
		if arr[i]==1:
			ans+=c[i][0]
	return ans

n,m,x = readInts()
c = []
for i in range(n):
	c.append(readInts())

ans = 1000000000000

for arr in bitArr(n):
	tmp = [0]*m
	for i in range(n):
		if arr[i]==1:
			arrsSum(tmp,c[i][1:])
	if min(tmp)>=x:

		kari = money(arr)
		if kari<ans:
			ans = kari

if ans==1000000000000:
	ans = -1

print(ans)

Submission status: Accepted

Solution code:
def resolve():

    n, m,x = map(int, input().split())
    c=[]
    a=[]
    ans=10**13
    nedan=0
    rikai=[0]*m
    for i in range(n):
        A = list(map(int, input().split()))
        c.append(A[0])
        a.append(A[1:])
        for j in range(m):
            rikai[j]+=a[i][j]

    if min(rikai)>=x:
        for Bin in range(1,2**n):
            rikai = [0] * m
            nedan = 0
            for hon in range(n):
                if (Bin>>hon) & 1:
                    for aru in range(m):
                        rikai[aru]+=a[hon][aru]
                    nedan+=c[hon]
            if min(rikai)>=x:
                ans=min(ans,nedan)
        print(ans)

    else:
        print(-1)
resolve()

Submission status: Accepted

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

mi = 1 << 100
for binary in range(1 << N):
    B = [0] * M
    c = 0
    for i in range(N):
        if binary >> i & 1:
            c += C[i]
            for j in range(M):
                B[j] += A[i][j]
    if min(B) >= X:
        mi = min(c, mi)
print(mi if mi < 1 << 99 else -1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

# l = list(range(0, n))
# print(l)

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

l = [True, False]
    
# print(l)

value_list = []
for is_buy_list in itertools.product(l, repeat=n):
    sum_l = np.array([0] * (m + 1))
    for i in range(n):
        # print(ll[i])
        if is_buy_list[i]:
            sum_l += np.array(ca_list[i])
            # print(sum_l)

    # print(min(sum_l[1:]))
    if min(sum_l[1:]) >= x:
        # print(sum_l[0])
        value_list.append(sum_l[0])
# print(min(value_list))

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

Submission status: Accepted

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

anslis = [1000000000000] * (2**N)

for i in range(2**N):
    kin = 0
    skil = [0] * M
    for j in range(N):
        if((i >> j) & 1):
            kin = kin + list[j][0]
            for k in range(M):
                skil[k] = skil[k] + list[j][k+1]

    if min(skil) >= X:
        anslis[i] = kin

if min(anslis) == 1000000000000:
    print(-1)
else:
    print(min(anslis))

Submission status: Accepted

Solution code:
def DFS(v):
    global rst
    if v<=N:
        L.append(v)
        DFS(v+1)
        L.pop()
        DFS(v+1)
    else:
        cost=[0]*M
        for i in L:
            for j in range(M):
                cost[j]+=CA[i-1][j+1]

        for i in range(M):
            if cost[i]<X:
                break
        else:
            out=0
            for j in L:
                out+=CA[j-1][0]
            rst=min(rst,out)

N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for _ in range(N)]
rst=10**9
L=[]

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

Submission status: Accepted

Solution code:
DEBUG = False

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

if DEBUG:
    print(A)
    print(C)

max_money = 10**5 * N + 1
ans_money = max_money
# ans_algorythm = None
for i in range(2**N):
    bit = bin(i)[2::]
    bit = bit.zfill(N)
    if DEBUG:
        print("i: {}, bit: {}".format(i, bit))
    tmp_money = 0
    tmp_algorythm = [0] * M
    for j, b in enumerate(bit):
        if b == '1':
            tmp_money += C[j]
            for k, c in enumerate(A[j]):
                tmp_algorythm[k] += c
    if DEBUG:
        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)
        if DEBUG:
            print("ans_money: {}".format(ans_money))
        # break

if ans_money == max_money:
    print(-1)
else:
    print(ans_money)

Submission status: Accepted

Solution code:
import numpy as np

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

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

cost = float("inf")

for i in range(2**N):
    buy = np.zeros(M+1)
    for j in range(N):
        if ((i >> j)&1):
            buy += C[j]
        if np.all(buy[1:] >= X):
            cost = min(cost, buy[0])

if cost == float("inf"):
    print(-1)
else:
    print(int(cost))

Submission status: Accepted

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


ans = 10**10
for b in range(2**n):
  skils = [0]*m
  tmp = 0
  
  for i in range(n):
    if b&(1<<i):
      for j in range(m):
        skils[j] += li[i][j+1]
      tmp += li[i][0]

        
  if min(skils)>=x:
    ans = min(ans, tmp)

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

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int,input().split(" "))
books = []
for i in range(n):
    books.append(list(map(int,input().split(" "))))
min_cost = 12*10**5+1
book_list = list(itertools.product(range(2),repeat = n))
for book in book_list:
    skills = [x for i in range(m)]
    cost = 0
    for j in range(len(book)):
        if book[j] == 1:
            cost += books[j][0]
            for k in range(m):
                skills[k] -= books[j][k+1]
    flag = True
    for j in range(m):
        if skills[j] > 0:
            flag = False
    if flag and cost != 0:
        min_cost = min(min_cost,cost)
if min_cost == 12*10**5+1:
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

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

l = list()
ans = []

for i in range(0, n):
    a_list.append(list(map(int, input().split())))


for i in range(1, 2**n):
    num = format(i, '0' + str(n) + 'b')
    l.append(num)

# print(l)

list_len = len(l)

s = 0

tmp = [0]*(m+1)

for i in range(0, list_len):
    w_len = m
    num = l[i]
    for j in range(0, n):
        if int(num[j]) == 1:
            for z in range(0, m+1):
                tmp[z] += a_list[j][z]
    # print(tmp)
    if len(list(filter(lambda number: number >= x, tmp[1:]))) == m:
        ans.append(tmp[0])
    tmp = [0]*(m+1)

# print(ans)

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections

def solve(N,M,X,C,A):
    ans = []
    for bit in range(2**N):
        total = 0
        dic = {key:0 for key in range(M)}
        for i in range(N):
            if(bit & (1 << i)):
                total += C[i]
                for n,a in enumerate(A[i]):
                    dic[n]+=a
        for m in range(M):
            if(dic[m] < X):
                break
        else:
            ans.append(total)
    return min(ans) if(ans != []) else -1
    # lis = [i for i in range(N)]
    # ans = []
    # for k,_ in enumerate(lis,1):
    #     for c in itertools.combinations(lis,r=k):
    #         tmp = 0
    #         dic = {key:0 for key in range(M)}
    #         for i in set(c):
    #             tmp += C[i]
    #             for n,a in enumerate(A[i]):
    #                 dic[n] += a
    #         for m in range(M):
    #             if(dic[m] < X):
    #                 break
    #         else:
    #             ans.append(tmp)
    # return min(ans) if(ans != []) else -1
def main():
    N,M,X = map(int,input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int,input().split()))
        C.append(tmp.pop(0))
        A.append(tmp)
    # solve()
    print(solve(N,M,X,C,A))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
books = {}
for i in range(N):
    books[i] = list(map(int,input().split()))

min_ = 10**10

for i in range(2**N):
    understanding = [0 for j in range(M)]
    cost = 0
    for j in range(N):
        if (i>>j)&1:
            for k in range(M):
                understanding[k] += books[j][k+1]
            cost += books[j][0]
    if all([a >= X for a in understanding]):
        min_ = min(min_,cost)

if min_ == 10**10:
    min_ = -1
print(min_)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, X = map(int, input().split())
    C = []
    A = []
    for _ in range(N):
        B = list(map(int, input().split()))
        C.append(B[0])
        A.append(B[1:])
    answer = float("inf")
    for i in range(2 ** N):
        ans = [0] * M
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                for m in range(M):
                    ans[m] += A[j][m]
                cnt += C[j]
        c = 0
        for m in range(M):
            if ans[m] >= X:
                c += 1
        if c == M:
            if cnt < answer:
                answer = cnt
    if answer == float("inf"):
        print(-1)
    else:
        print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

def main():
    N, M, X = [int(i) for i in input().split()]
    C, A = [], []
    for _ in range(N):
        ca = [int(i) for i in input().split()]
        C.append(ca[0])
        A.append(ca[1:])

    for m in range(M):
        if sum(a[m] for a in A) < X:
            print(-1)
            return

    sets = []
    comb_ix = [comb for i in range(1, len(A) + 1) for comb in combinations(range(len(A)), i)]
    for m in range(M):
        tmp_lst = []

        for comb in comb_ix:
            a = [a[m] for i, a in enumerate(A) if i in comb]
            if sum(a) >= X:
                tmp_lst.append(comb)
        
        sets.append(frozenset(tmp_lst))

    intersection = set.intersection(*map(set, sets))
    res = sum(C)
    for comb in intersection:
        sum_c = sum(c for i, c in enumerate(C) if i in comb)
        if sum_c < res:
            res = sum_c

    print(res)

main()

Submission status: Accepted

Solution code:
def resolve():
    n, m, x = map(int, input().split())
    A, C = [], []
    for _ in range(n):
        c_a = list(map(int, input().split()))
        c = c_a.pop(0)
        A.append(c_a)
        C.append(c)

    def dfs(N, B, D):
        if N == n:
            if min(B) < x:
                return -1
            else:
                return D
        r = dfs(N + 1, [x + y for (x, y) in zip(B, A[N])], D + C[N])
        l = dfs(N + 1, B, D)
        if l == r == -1:
            return -1
        else:
            if l == -1:
                return r
            elif r == -1:
                return l
            else:
                return min([l, r])

    print(dfs(0, [0 for i in range(m)], 0))
resolve()

Submission status: Accepted

Solution code:
def resolve():
    import itertools

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

    prices = []
    gains = []
    for i in range(n):
        price, *gain = list(map(int, input().split()))
        prices.append(price)
        gains.append(gain)

    combs = []
    for i in range(n + 1):
        for comb in itertools.combinations(list(range(n)), i):
            combs.append(comb)

    successful = []
    for comb in combs:
        levels = [0] * m
        sum = 0

        for i in comb:
            sum += prices[i]
            for j in range(m):
                levels[j] += gains[i][j]

        levels = list(filter(lambda item: item >= x, levels))
        if len(levels) == m:
            successful.append(sum)

    print(min(successful)) if len(successful) != 0 else print(-1)
resolve()

Submission status: Accepted

Solution code:
import numpy as np

N,M,X = map(int, input().split(' '))
C=[]
maxNum=999999999
dmaxNum=999999999
for i in range(N):
  C.append(list(map(int, input().split(' '))))
for i in range(2**N):
  ar=[0]*(M+1)
  for j in range(N):
    if (i & 2**j) != 0:
      ar = [x + y for (x, y) in zip(ar, C[j])]
  if (np.array(ar[1:])>=X).all()>0:
    maxNum=min(maxNum,ar[0])
if maxNum==dmaxNum:
  print(-1)
else:
  print(maxNum)

Submission status: Accepted

Solution code:
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

def read_int_list():
    return list(map(int,input().split(' ')))

def read_s_list_loop(n):
    return [input() for _ in range(n)]

def bit_cal(n):
    return_list = ['']* (2 ** n)
    for i in range(2 ** n):
        for j in range(n):
            if ((i >> j) & 1):
                return_list[i] = return_list[i] + '1'
            else:
                return_list[i] = return_list[i] + '0'
    return return_list

N,M,X = read_int_map()
Cn = [list(read_int_map()) for _ in range(N) ]

ans = float('inf')
bit_list = bit_cal(N)
for bit in bit_list:
    m_list = [0]*M
    price = 0
    for i in range(N):
        if bit[i] == '1':
            price += Cn[i][0]
            for j in range(1,M+1):
                m_list[j-1] += Cn[i][j]
    flag = True
    for m in m_list:
        if m < X:
            flag = False
            break
    if flag:
        ans = min(price,ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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

INF = 10**9
ans = INF
for s in range(0, 1 << N):
    smart = [0] * M
    cost_sum = 0
    for i in range(N):
        if (s >> i) % 2 == 0:
            continue
        cost_sum += C[i]
        for j in range(M):
            smart[j] += A[i][j]
    ok = True
    for j in range(M):
        if smart[j] < X:
            ok = False
    if ok:
        ans = min(ans, cost_sum)
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n, m, x = MAP()
arr = [LIST() for _ in range(n)]
c = [arr[i][0] for i in range(n)]
a = [arr[i][1:] for i in range(n)]

ans = inf
for i in range(2 ** n):
    tmp = [0 for _ in range(m)]
    cst = 0
    for j in range(n):
        if i - (i >> (j + 1)) * (2 ** (j + 1)) >= 2 ** j:
            for k in range(m):
                tmp[k] += a[j][k]
            cst += c[j]
    flag = True
    for j in range(m):
        if tmp[j] < x:
            flag = False
    if flag:
        ans = min(ans, cst)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

INF = float("inf")
ans = INF

for i in range(2**n):
    A = [0] * m
    price = 0

    # j番目の本について
    for j in range(n):
        if i>>j & 1:
            price += ca[j][0]
            for k in range(m):
                A[k] += ca[j][k+1]

    gtX = True
    for j in range(m):
        if A[j] < x:
            gtX = False
            break
    if gtX:
        ans = min(ans, price)

if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

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

for i in range(N):
    line = list(map(int, input().split()))
    C[i] = line[0]
    for j in range(M):
        A[i].append(line[j+1])
ans = INF

for bit in range(2**17):
    sum = 0
    skill = [0] * M
    for i in range(N):
        if random.randint(0, 1):
            sum += C[i]
            for j in range(M):
                skill[j] += A[i][j]
    ok = True
    for j in range(M):
        if skill[j] < X:
            ok = False
    if ok:
        ans = min(ans, sum)
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

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

ans = 1<<60

for i in range(1<<n):
    score = [0]*m
    money = 0
    for j in range(n):
        if (1<<j) & i != 0:
            money += c[j]
            for k in range(m):
                score[k] += a[j][k]
    if min(score) >= x:
        ans = min(ans,money)

if ans == 1<<60:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
INF = 10**9

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

choose = [True, False]

min_price = INF

for s in product([True, False], repeat=N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if s[i]:
            knowledge += A[i]
            price += C[i]
    if np.any(knowledge < X):
        continue
    if min_price == -1:
        min_price = price
    min_price = min(min_price, price)

if min_price == INF:
    print(-1)
else:
    print(min_price)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M, X  = [int(x) for x in stdin.readline().rstrip().split()]

CA = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

dp = [[[0 for _ in range(M)] for _ in range(4)] for _ in range(N+1)]
dp_money = [[0 for _ in range(2)] for _ in range(N+1)]

tm = [0 for _ in range(2**N)] 
tl = [[0 for _ in range(M)] for _ in range(2**N)]

knowledge_list = [[0 for _ in range(M)]]
money_list = [0]

for i in range(N):
    C = CA[i][0]
    A = CA[i][1:]

    # 購入する場合
    tmp2 = []
    
    for i, knowledge in enumerate(knowledge_list):
        tmp = []
        for k in range(len(knowledge)):
            tmp.append(knowledge[k] + A[k])
        
        tmp2.append(tmp)
        money_list.append(money_list[i]+C)

    knowledge_list = knowledge_list + tmp2

ans = INF
for i in range(len(money_list)):
    if min(knowledge_list[i]) >= X:
        ans = min(ans, money_list[i])

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

Submission status: Accepted

Solution code:
import math
from sys import stdin,stdout
#% 998244353
from heapq import heapify,heappop,heappush

from collections import Counter
#T = int(stdin.readline())
#for i in range(T):

    #N=int(stdin.readline())

def helper(bks,p,cc,alg,vis,m,n,x):
    
    if p==n:
        f=True
        for i in range(m):
            if alg[i]<x:
                f=False
                break
        if f:
            return cc
        return float('inf')    
    ans=float('inf')
    for b in range(p,n):
    #    if b not in vis:
    #        vis.add(b)
        for i in range(m):
            alg[i]+=bks[b][i+1]
        
        ans=min(ans,helper(bks,b+1,cc+bks[b][0],alg,vis,m,n,x) )
        #print(ans)
        for i in range(m):
            alg[i]-=bks[b][i+1]
    #       vis.remove(b)
    ans=min(ans,helper(bks,n,cc,alg,vis,m,n,x) )
    return ans


n,m,x=list(map(int,stdin.readline().split()))
bks=[[0]*(m+1) for _ in range(n)]

for i in range(n):
    bks[i]=list(map(int,stdin.readline().split()))
    

pos=True

alg=[0]*m
for i in range(n):
    for j in range(m):
        alg[j]+=bks[i][j+1]
#print(alg,x)
for i in range(m):
    if alg[i]<x:
        pos=False
        break



if not pos:
    print(-1)
else:
    alg=[0]*m
    print(helper(bks,0,0,alg,set(),m,n,x))

Submission status: Accepted

Solution code:
import numpy as np
import sys
from itertools import chain, combinations

N, M, X = [int(n) for n in input().split()]

matrix = np.zeros((N,M+1))
for i in range(N):
    matrix[i] = np.array([int(n) for n in input().split()])

total = np.sum(matrix[:,1:],axis=0)
if not all(i >= X for i in total):
    print(-1)
    sys.exit(0)

def checkthresh(A, thresh):
    return all(i >= thresh for i in A)

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1,len(s)+1))

cost = N*10**5
for subset in powerset(range(N)):
    sum_subset = np.zeros((1,M+1))
    for i in subset:
        sum_subset += matrix[i,:]
    sum_subset = sum_subset[0]
    if checkthresh(sum_subset[1:], X):
        cost = min(cost, sum_subset[0])

print(int(cost))