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:
#https://atcoder.jp/contests/abc167/tasks/abc167_c C - Skill Up
import numpy as np
import math
from itertools import combinations
N,M,X=list(map(int,input().split()))
book_dict={}
for i in range(N):
    book_dict[i] = list(map(int,input().split()))

answer = (10**5*12)+1
for i in range(N,0,-1):
    current_book_number=0    
    for v in combinations(book_dict.keys(), i):
        ##要件を満たさない組み合わせカウント
        search_book = list(map(lambda x:book_dict[x],list(v)))
        sum_search_book = np.array(np.sum(search_book,axis = 0))
        if (np.count_nonzero(sum_search_book[1:] >= X) == M) and sum_search_book[0] < answer:
            answer = sum_search_book[0]
        else:
            current_book_number+=1
    ##どの組み合わせでも達成できない場合は、これ以上本を減らしても意味ない    
    if current_book_number==int(math.factorial(N)/(math.factorial(i)*math.factorial(N-i))):
        break                                                                                 
    
if answer == (10**5*12)+1:
    answer = -1

print(answer)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc167/tasks/abc167_c C - Skill Up
import numpy as np
from itertools import combinations
N,M,X=list(map(int,input().split()))
book_dict={}
for i in range(N):
    book_dict[i] = list(map(int,input().split()))

answer = (10**5*12)+1
for i in range(N,0,-1):
    for v in combinations(book_dict.keys(), i):
        search_book = list(map(lambda x:book_dict[x],list(v)))
        sum_search_book = np.array(np.sum(search_book,axis = 0))
        if (np.count_nonzero(sum_search_book[1:] >= X) == M) and sum_search_book[0] < answer:
            answer = sum_search_book[0]
                                                                                 
    
if answer == (10**5*12)+1:
    answer = -1

print(answer)

Submission status: Accepted

Solution code:
[n, m, x], *t = [[*map(int, t.split())] for t in open(0)]
ans = 1200001
for i in range(1, 2**n):
    tmp = [t[k] for k in range(n) if 1 << k & i]
    c, *a = map(sum, zip(*tmp))
    if min(a) >= x:
        ans = min(ans, c)
if ans == 1200001:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
#C bit
import numpy as np

N, M, X = list(map(int, input().split()))
C = []
A = np.zeros((N, M), dtype=int)

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

result = -1
for i in range(1 << N):
    reading_books = np.zeros((M), dtype=int)
    cost = 0
    for j in range(N):
        if not (i >> j) & 1:
            continue
        cost += C[j]
        reading_books += A[j, :]
    if all(reading_books >= X):
        if result == -1:
            result = cost
        else:
            result = min(cost, result)


print(result)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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


result = -1
anp = np.array(a)
sum = sum(c)


    
for i in itertools.product([0,1],repeat=n):
    each_cost =0
    ans =anp.T*i
#    print(ans)
#    print(ans.sum(axis=1))
    if min(ans.sum(axis=1))>=x:
        sum = min(np.dot(c,i),sum)
        result = 0

#print(result)
#print(sum)
if result ==0:
    print(sum)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np 
from itertools import combinations
N,M,X = (int(x) for x in input().split())
C =np.zeros(N,dtype=int)
#A ={i:[] for i in range(1,M+1)}
A =np.zeros((N,M),dtype=int)
for i in range(N):
    x,*y = (int(x) for x in input().split())
    C[i] =x
    A[i] =np.array(y,dtype=int)

#何冊買うか、どれを買うか全探索
ans =[]
for i in range(1,N+1): #何冊買うか
    for j in combinations(range(N),i): #どの本を買うか
        understanding =np.sum(A[j,],axis=0)
        if np.all(understanding >=X):
            z =np.sum(C[j,])
            ans.append(z)
        #print(j,understanding)
        #print(j,end="- ")
if len(ans) >0:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X =map(int,input().split())
A =[]
for m in range(N):
    A.append([int(j) for j in input().split()])
ans = 10**10
import numpy as np
from itertools import product,compress
for i in list(product([True,False],repeat=N)):
    tmp = np.sum(list(compress(A, i)),axis=0)
    if type(tmp)!=np.float64:
    	if tmp[0]< ans and min(tmp[1:])>=X:
            ans =tmp[0]
if ans ==10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def f(p):
    bp=bin(p)[2:].zfill(n)
    tmp=[x]+[0 for _ in range(m)]
    cost=0
    for i in range(n):
        if bp[i]=="0": continue
        cost+=skill[i][0]
        for j in range(1,m+1):
            tmp[j]+=skill[i][j]
    return cost if min(tmp)>=x else 10**15

n,m,x=map(int,input().split())
skill=[list(map(int,input().split())) for _ in range(n)]
ans=10**15
for p in range(2**n):
    ans=min(ans,f(p))
print(ans if ans<10**15 else -1)

Submission status: Accepted

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

costl = []

for p in itertools.product([0,1],repeat=N):
    f = [0]*M
    cost = 0
    for i in range(N):
        if p[i] == 1:
            for j in range(M):
                f[j] += arr[i][j+1]
            cost += arr[i][0]
    if all(point >= X for point in f):
        costl.append(cost)

print(min(costl) if len(costl) >= 1 else -1)

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):
    C[i], *A[i] = map(int, input().split())
MAX = 10**5 * 12 + 1
minprice = MAX
for b in range(2**N):
    abilityList = [0]*M
    price = 0
    for i in range(N):
        if b >> i & 1 == 1:
            abilityList = [x+y for (x,y) in zip(abilityList, A[i])]
            price += C[i]
    judge = True
    for ability in abilityList:
        if ability < X:
            judge = False
    if judge:
        minprice = min(minprice, price)
ans = minprice if minprice != MAX else -1
print(ans)

Submission status: Accepted

Solution code:
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n, m, x = 3, 3, 10
    C = [60, 70, 50]
    A = [[2, 2, 4], [8, 7, 9], [2, 3, 9]] 

  else:
    ##INPUT 
    #n = input()
    n, m, x = map(int, input().split())
    C = []
    A = []
    for _ in range(n):
      tmp = list(map(int, input().split()))
      C.append(tmp[0])
      A.append(tmp[1:])

  ## SUBMITION CODES HERE
  ans = f_inf
  for s in range(1<<n): # 1<<n: 2^n 
    cost = 0
    D = [0] * m
    for i in range(n):
        if s>>i & 1: # Shift s by i times to the right and check if the least significant digit is 1
            cost += C[i]
            for j in range(m):
                D[j] += A[i][j]
    
    flg = True
    for d in D:
        if d < x: flg = False
    if flg: ans = min(ans, cost)

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

main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
book=[0]*n
for i in range(0,n):
  book[i]=list(map(int,input().split()))
total=[]
for i in range(2**n):
  cost=0
  rikai=[0]*m
  for j in range(n):
    if (i >> j)&1:
      for k in range(m):
        rikai[k] += book[j][k+1]
      cost+=book[j][0]
  if all(l >= x for l in rikai):
    total.append(cost)

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

Submission status: Accepted

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

C = []
A = []
for i in range(N):
    # この1行をtとする
    t = list(map(int, input().split()))
    C.append(t[0])
    # c以降はそれぞれAに代入
    A.append(t[1:])

result = -1
for i in range(1 << N):
    # 0をm個分複製
    t = [0] * M
    c = 0
    for j in range(N):
        # i を j回右にシフトして 1 と論理積を取る　これがfalseならcontinue
        if (i >> j) & 1 == 0:
            continue
        # trueならc[j]円カウントする　最終的に180円になる
        c += C[j]
        for k in range(M):
            # Aj冊目のkをリストtにいれる 0 1 2 と順番に
            t[k] += A[j][k]
    # xが指定のXの理解度に達するまで上のtをチェック
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Submission status: Accepted

Solution code:
import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

N, M, X, *CA = map(int, read().split())
CA = tuple(zip(*[iter(CA)] * (M + 1)))
answer = 10 ** 10
for i in product((0, 1), repeat=N):
    m = 0
    s = [0] * M
    for j in range(N):
        if i[j] == 1:
            m += CA[j][0]
            for k in range(M):
                s[k] += CA[j][k + 1]
    if all(j >= X for j in s):
        if answer > m:
            answer = m

if answer == 10 ** 10:
    print(-1)
else:
    print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000000)
INF = int(1e9)

#ans:=目標達成するのに必要な最小の金額（求める値）
#最小値を更新しながら求めていくので初期値は十分大きな数とする
ans = INF
def main():
    N, M, X = map(int, readline().split())

    #参考書、アルゴリズムは0-indexed

    #costs[i]:=参考書iの金額
    #score[i][j]:=参考書iを読んで上がるアルゴリズムjの理解度
    costs = []
    score = []
    for _ in range(N):
        c, *d = map(int, readline().split())
        costs.append(c)
        score.append([i for i in d])

    #bit:=どの参考書を買うかの組み合わせを表現するリスト
    #bit[i]が1のときi番目の参考書を買う
    #bit[i]が0のときi番目の参考書を買わない
    bit = []
    #買う参考書の組みを順に全て構成し、構成した組それぞれに対して金額の総和計算をする
    def dfs():
        global ans
        #全てのbitの0,1が決まる=購入する参考書の組みが決定したとき理解度の計算をする
        if len(bit) == N:
            #cost:=買った参考書の値段の合計金額 
            cost = 0
            #sumSocore[i]:=i番目のアルゴリズムの理解度の累計 
            sumScore = [0 for _ in range(M)]
            for i in range(N):
                if bit[i]:
                #bit[i]==1なら参考書iを購入するのでcostを更新する
                    cost += costs[i]
                    for j in range(M):
                        #sumScoreを更新
                        sumScore[j] += score[i][j]

            #全てのアルゴリズムの理解度がx以上であるかの判定
            #flag:=全てのアルゴリズムの理解度がx以上であるか
            flag = True 
            for i in range(M):
                if sumScore[i] < X: 
                    flag = False

            #全てのアルゴリズムの理解度がx以上であるときcostはansの候補である
            if flag:
                #cost < ansのときcostをansに代入
                ans = min(ans, cost)
                return 
            return 

        #bit全探索の核となる部分
        #bitを決めていく.0か1を追加していく（括弧内はi=1のときの説明）
        for i in range(2): 
            #初めのループでi=0をappendする（次のループでi=1をappendする）
            bit.append(i)
            #0がappendされた状態で次の深さのdfsを走らせる.（1がappendされた状態で次の深さのdfsを走らせる）
            dfs()
            #次のループでi=1を同じ位置へappendするために0をpopしておく（i=1をpopすることに意味はないので無駄な処理となる）
            bit.pop()

    dfs()
    if ans == INF:
        print(-1)
    else:
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000000)
INF = int(1e9)

#ans:=目標達成するのに必要な最小の金額（求める値）
#最小値を更新しながら求めていくので初期値は十分大きな数とする
ans = INF
def main():
    N, M, X = map(int, readline().split())

    #参考書、アルゴリズムは0-indexed

    #costs[i]:=参考書iの金額
    #score[i][j]:=参考書iを読んで上がるアルゴリズムjの理解度
    costs = []
    score = []
    for _ in range(N):
        c, *d = map(int, readline().split())
        costs.append(c)
        score.append([i for i in d])

    #bit:=どの参考書を買うかの組み合わせを表現するリスト
    #bit[i]が1のときi番目の参考書を買う
    #bit[i]が0のときi番目の参考書を買わない
    bit = []
    #買う参考書の組みを順に全て構成し、構成した組それぞれに対して金額の総和計算をする
    def dfs():
        global ans
        #全てのbitの0,1が決まる=購入する参考書の組みが決定したとき理解度の計算をする
        if len(bit) == N:
            #cost:=買った参考書の値段の合計金額 
            cost = 0
            #sumSocore[i]:=i番目のアルゴリズムの理解度の累計 
            sumScore = [0 for _ in range(M)]
            for i in range(N):
                if bit[i]:
                #bit[i]==1なら参考書iを購入するのでcostを更新する
                    cost += costs[i]
                    for j in range(M):
                        #sumScoreを更新
                        sumScore[j] += score[i][j]

            #全てのアルゴリズムの理解度がx以上であるかの判定
            #flag:=全てのアルゴリズムの理解度がx以上であるか
            flag = True 
            for i in range(M):
                if sumScore[i] < X: 
                    flag = False

            #全てのアルゴリズムの理解度がx以上であるときcostはansの候補である
            if flag:
                #cost < ansのときcostをansに代入
                ans = min(ans, cost)
                return 
            return 

        #bitを決めていく0か1を追加していく
        for i in range(2): 
            bit.append(i)
            dfs()
            #次のループでi=1を同じ位置へappendするためにpopしておく
            bit.pop()

    dfs()
    if ans == INF:
        print(-1)
    else:
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Books = []
Skills = [0] * M
cost = 0
res = 10 ** 9

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

for bit in range(2 ** N):
    for i in range(N):
        if (bit >> i) & 1:
            for j in range(M):
                Skills[j] += Books[i][j+1]
            cost += Books[i][0]
    if all(a >= X for a in Skills):
        res = min(res, cost)
    cost = 0
    Skills = [0] * M

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

Submission status: Accepted

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

ans = float('inf')
for p in range(2 ** n):
    total = 0
    line = [0] * m
    for i in range(n):
        if (p >> i) & 1:
            for j in range(m):
                line[j] += a[i][j]
            total += c[i]
    if all((num >= x for num in line)):
        ans = min(ans, total)

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

Submission status: Accepted

Solution code:
import numpy as np
N,M,X = (int(x) for x in input().split())
Data  = np.zeros((N,M+1),dtype=int)
for Book in range(0,N):
    Data[Book,:] = np.array([int(x) for x in input().split()])

minCost = float('inf')
OK_Flag = 0
for Pt in range(0,pow(2,N)):
    strA  = (list(format(Pt,'0'+str(N)+'b')))
    intA  = np.array([int(x) for x in strA],dtype=bool)
    Price = np.sum(intA.reshape(N,1)*Data,axis=0)
    if (all(Price[1:]>=np.full(M,X))) & (Price[0]<minCost):
        minCost = Price[0]
        OK_Flag = 1

if OK_Flag:
    print(minCost)
else:
    print('-1')

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[]
A=[]
for _ in range(N):
    Y=list(map(int,input().split()))
    C.append(Y[0])
    A.append(Y[1:])
res=10**9
for bit in range(2**N):
    sums=0
    array=[0]*M
    for i in range(N):
        if bit>>i&1:
            for j in range(M):
                array[j]+=A[i][j]
            sums+=C[i]
    if all((a>=X for a in array)):
        res=min(res,sums)

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[]
A=[]
for _ in range(N):
    Y=list(map(int,input().split()))
    C.append(Y[0])
    A.append(Y[1:])
res=10**9
for bit in range(2**N):
    sums=0
    array=[0]*M
    for i in range(N):
        if bit>>i&1:
            for j in range(M):
                array[j]+=A[i][j]
            sums+=C[i]
    array.sort()
    if array[0]>=X:
        res=min(res,sums)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c=[]
a=[]
INF = float("inf")
stock = INF
for _  in range(n):
    c_temp,*a_temp = list(map(int,input().split()))
    c.append(c_temp)
    a.append(a_temp)

for bit in range(1 << n):
    cost_total = 0
    smart_total = [0]*m

    for i in range(n):
        if (bit >> i) & 1:
            # i冊目を買うときの処理
            smart = []
            cost_total += c[i]
            smart = a[i]
            for j , sm in enumerate(smart):
                smart_total[j] += sm
        #else:
            # i冊目を買わないときの処理（今回は何もしないので省略）
    judege = True
    for i in range(m):
        if smart_total[i] < x:
            judege = False
    if judege:
        stock = min(cost_total,stock)
if stock == INF:
    print("-1")
else:
    print(stock)

Submission status: Accepted

Solution code:

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

price_list = []
skillup = []
for i in range(n):
    book = list(map(int,input().split()))
    price_list.append(book[0])
    skill = []
    for j in range(m):
        skill.append(book[j+1])
    skillup.append(skill)

min_price = 10**10
for i in range(2**n):
    price = 0
    skill = [0] * m
    index = 0

    bits = "0" * (n - (len(bin(i))-2)) + str(bin(i))[2:len(bin(i))] 

    for bit in bits:
        if bit == "1":
            price += price_list[index]
            for s in range(m):
                skill[s] += skillup[index][s]
        index+=1
    check = [0] * m
    for s in range(m):
        if skill[s] >= x:
            check[s] = 1
    passed = 1
    for s in range(m):
        if check[s] == 0:
            passed = 0
    if passed:
        if price < min_price:
            min_price = price

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

Submission status: Accepted

Solution code:
#ABC167c

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

ans = 99999999
for i in range(2 ** N):
    bag = []
    for j in range(N):
        if ((i >> j) & 1):
            bag.append(book_list[j])
    total_cost = 0
    skill = [0] * M
    enough = [0] * M
    for subject in bag:
        total_cost += subject[0]
        for k in range(M):
            skill[k] += subject[k+1]
            if skill[k] >= X:
                enough[k] = 1
    if 0 not in enough:
        if ans > total_cost:
            ans = total_cost

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

Submission status: Accepted

Solution code:
import numpy as np

def dfs(n,a,s):
  if n==0:
    return -1 if (a >= X).all()==False else s
  #print(a+A[n-1])
  x=dfs(n-1,a+A[n-1],s+C[n-1])
  y=dfs(n-1,a,s)
  return y if x==-1 else x if y==-1 else min(x,y)

N,M,X=map(int,input().split())
C=[]
A=[]
for i in range(N):
  c,*tmp=map(int,input().split())
  A.append(np.array(tmp))
  C.append(c)
#print(A)
print(dfs(N,np.array([0]*M),0))

Submission status: Accepted

Solution code:
#include <CodeforcesSolutions.h>
#include <ONLINE_JUDGE_SOLUTION <solution.cf(contestID = "1359",problemID = "C",method = "GET")>.h>
"""
    Author : thekushalghosh
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,itertools
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################

def solve():
    ONLINE_JUDGE_SOLUTION = Codeforces.CodeforcesSolutions("1361","A","GET","POST")
    print(ONLINE_JUDGE_SOLUTION)
                
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
    sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return(q)

class Codeforces():
    def CodeforcesSolutions(id,question,get,post):
        n,m,x = invr()
        a = []
        c = []
        qwqw = []
        for i in range(n):
            s = inlt()
            c.append(s.pop(0))
            a.append(s)
        q = [i for i in range(n)]
        for i in range(n):
            w = list(itertools.combinations(q,i + 1))
            for j in range(len(w)):
                qw = w[j]
                qq = [0] * m
                ww = 0
                for k in range(len(qw)):
                    ww = ww + c[qw[k] - 1]
                    qq = [qq[l] + a[qw[k] - 1][l] for l in range(m)]
                if min(qq) >= x:
                    qwqw.append(ww)
        if qwqw:
            return(min(qwqw))
        return(-1)
                    


        q = min(a,d)
        w = min(b,d - q)
        qw = min(d - q - w,c)
        return(q - qw)
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

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())))
ans = 10 ** 7
t = 2 ** n
for i in range(t):
    s = [0 for _ in range(m)]
    c = 0
    bin_i = format(i, '012b')
    if len(bin_i) > n:
        bin_i = bin_i[12-n:]
    for j in range(n):
        if bin_i[j] == "1":
            for k in range(m):
                s[k] += A[j][k+1]
            c += A[j][0]
    if  c < ans and min(s) >= x:
        ans = c
if ans == 10 ** 7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m,x=map(int,input().split())
A=[[int(i) for i in input().split()] for _ in range(n)]
ans=float("inf")
for i in range(2**n):
  B=[0]*(m+1)
  for j in range(n):
    if i&(1<<j):
      for k in range(m+1):
        B[k]+=A[j][k]
  if min(B[1:])>=x:
    ans=min(ans,B[0])
print(-1 if ans==float("inf") else ans)

Submission status: Accepted

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

def xcheck(data):
    for i in range(1, m + 1):
        if data[i] < x:
            return False
    return True

def listup(n, m):
    d = []
    c = [i + 1 for i in range(n)]
    while True:
        d.append(tuple(c))
        if c == [m - n + i + 1 for i in range(n)]:
            break
        c[n - 1] += 1
        if c[n - 1] > m:
            for i in range(n - 1):
                if c[n - 2 - i] == m - i - 1:
                    continue
                c[n - i - 2] += 1
                for j in range(i + 1):
                    c[n - i - 1 + j] = c[n - i - 2] + j + 1
                break
    return d

dmin = -1
for i in range(1, n + 1):
    data = listup(i, n)
    for j in range(len(data)):
        cur = data[j]
        sumd = []
        for k in range(m + 1):
            s = 0
            for l in range(len(cur)):
                s += d[cur[l] - 1][k]
            sumd.append(s)
        if xcheck(sumd) == True:
            if (dmin == -1) | (sumd[0] < dmin):
                dmin = sumd[0]

print(dmin)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
ls=[list(map(int,input().split())) for i in range(N)]
ls_c=[]
for i in range(1,2**N):
  ls_al=[0]*M
  c=0
  for j in range(N):
    if (i>>j)&1==1:
      c+=ls[j][0]
      for k in range(M):
        ls_al[k]+=ls[j][k+1]
  if min(ls_al)>=X:
    ls_c.append(c)
    
if ls_c!=[]:
  print(min(ls_c))
else:
  print(-1)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
import numpy as np
pr = []
score = []

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

cnt =0
ans = 10**10
for i in range(1<<n):
    tot = np.array([0]*m)
    pr_all = 0
    for j in range(n):
        if i>>j&1:
            score[j] = np.array(score[j])
            tot +=np.array(score[j])
            pr_all +=pr[j]

    if np.all(tot >=k):
        ans = min(ans,pr_all)
        
print(ans if ans <10**10 else -1)

Submission status: Accepted

Solution code:
import sys
#import cython

def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    N, M, X  = map(int,read().split())
    A = [list(map(int,read().split())) for i in range(N)]

    pattern = []
    ans = []
    for i in range(2**(N)):
        tmp = [1]*N
        for j in range(N):
            if i >> j & 1:
                tmp[j] = 0
        tab = [0]*(M)
        tot = 0
        for j in range(N):
            for k in range(M):
                tab[k] += A[j][k+1]*tmp[j]
            tot += A[j][0]*tmp[j]
        if min(tab) >= X:
            ans.append(tot)
    
    print(min(ans) if ans != [] else -1)

 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""N冊の参考書 M個のアルゴリズム 理解度X"""
N, M, X = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

bit =[]
for i in range(2 ** N):
    tmp = [0]*N
    for k in range(N):
        if 1 & i>>k:
            tmp[k] = 1
    bit.append(tmp)

ans = float('inf')
for list in bit:
        money =0
        rikai = [0]*M
        for i in range(N):
            if list[i] == 1:
                money += arr[i][0]
                for j in range(M):
                    rikai[j] += arr[i][j+1]
        if min(rikai)>=X:
            ans = min(ans, money)

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

Submission status: Accepted

Solution code:

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

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

money = []
for i in range(M):
    money.append(0)

res = 10**10
for bits in range(2**N):
    tmp = 0
    for i in range(M):
        money[i] = 0

    for i in range(N):
        if (bits>>i)&1:
            tmp+=C[i]
            for j in range(M):
                money[j]+=A[i][j]
    jadge = True
    for i in range(M):
        if money[i] < X:
            jadge = False

    if jadge:
        res = min(tmp,res)

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

Submission status: Accepted

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

ans = 10**9
for i in range(1,n+1):
  for j in combinations(ca, i):
    s = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        s[l] += k[l]
    if min(s[1:]) >= x:
      ans = min(ans, s[0])
if ans == 10**9:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
costl=[]
for p in itertools.product([0,1],repeat=n):
  al=[0]*m
  cost=0
  for i in range(n):
    if p[i]==1:
      cost+=l[i][0]
      for j in range(1,m+1):
        al[j-1]+=l[i][j]
  if all(mm>=x for mm in al):
    costl.append(cost)
print(min(costl) if len(costl)>=1 else -1)

Submission status: Accepted

Solution code:
def twodig(x, N):
  l = list(bin(x))
  n = len(l)- 2
  ans = []
  for i in range(N- n):
    ans.append(0)
  for i in range(2, n+ 2):
    ans.append(int(l[i]))
  return ans

N, M, X = map(int, input().split())
lista = []
for i in range(N):
  lista.append(list(map(int, input().split())))
  
count = 1
ans = []

for i in range(2** N):
  flag = 0
  r = twodig(count, N)
  newlista = []
  c = r.count(1)
  for j in range(c):
    index = r.index(1)
    r[index] = 0
    newlista.append(lista[index])
  for k in range(1, M+ 1):
    summ = 0
    for l in range(c):
      summ+= newlista[l][k]
    if(summ < X):
      ans.append(-1)
      flag = 1
      break
  if(flag == 1):
    count+= 1
    continue
  else:
    cuota = 0
    for i in range(c):
      cuota+= newlista[i][0]
    ans.append(cuota)
    count+= 1
    
Ans = list(filter(lambda x: x!= -1, ans))

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

Submission status: Accepted

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

c=[]
for i in range(2**N):
  cost=0
  point=[0 for i in range(M)]
  i=format(i,'b')
  i=i.rjust(N,'0')
  for j in range(N):
    if i[j]=='1':
      cost+=g[j][0]
      for k in range(M):
        point[k]+=g[j][k+1]
        
    if all(i>=X for i in point):
      c.append(cost)
if c==[]:
  print(-1)
else:
  print(min(c))

Submission status: Accepted

Solution code:
#abc167c
n,m,x=map(int,input().split())
mt=[list(map(int,input().split())) for i in range(n)]
res=[-1]*(m+1)
temp=[0]*(m+1)
for i in range(1<<n):
  for j in range(n):
    if (i>>j)&1:
      for k in range(m+1):
        temp[k]+=mt[j][k]
  for j in range(1,m+1):
    if temp[j]<x:
      break
  else:
    if res[0]>temp[0] or res[0]<0:
      res=temp
  temp=[0]*(m+1)
print(res[0])

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
arr = []
for i in range(N):
    arr.append(list(map(int,input().split())))
cost = 10**9 + 7
for k in range(2**N):
    c = 0
    t = [0]*M
    for i in range(N):
        if (k >> i)%2 :
            c += arr[i][0]
            for j in range(M):
                t[j] += arr[i][j+1]
    if sum(x>=X for x in t) == M:
        cost = min(cost,c)
print(cost if cost < 10**9 + 7 else -1)