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())
c, a = [0] * n, [[] for _ in range(n)]
for i in range(n):
    s = list(map(int, input().split()))
    c[i] = s[0]
    a[i] = s[1:]
# bit全探索
ans = 10 ** 7  # INF
for i in range(2 ** n):
    score = [0] * m
    cost = 0
    for j in range(n):
        if i >> j & 1:
            cost += c[j]
            for k in range(m):
                score[k] += a[j][k]
    if len([i for i in score if i < x]) == 0:
        ans = min(ans, cost)
if ans == 10 ** 7:
    print(-1)
else:
    print(ans)

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**10
for i in range(1,n+1):
  for j in combinations(ca,i):
    check = [0]*(m+1)
    for k in j:
      for a in range(m+1):
        check[a] += k[a]
    if min(check[1:]) >= x:
      ans = min(ans, check[0])

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
price = 10**100
l = []

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

for j in range(2**n):
    s = [0 for _ in range(m+1)]
    s[0] += x
    for k in range(n):
        if ((j>>k)&1):
            for o in range(m+1):
                so = s[o]
                lo = l[k][o]
                s[o] = so + lo
    if all( q >= x for q in s):
        z = s[0] - x
        if price > z:
            price = z

if price == 10**100:
    price = -1
print(price)

Submission status: Accepted

Solution code:
import itertools

def main():
    n, m, x = map(int, input().split())
    ca = [list(map(int, input().split())) for i in range(n)]
    INF = float('INF')
    res = INF
    for comb in itertools.chain(*(itertools.combinations(ca,r) for r in range(1,n+1))):
        c, *a = list(map(sum, zip(*comb)))
        if c < res and min(a) >= x:
            res = c
    if res == INF:
        print(-1)
    else:
        print(res)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

c = [[]]*N
a = [[[]]*M]*N

for n in range(N):
    temp = list(map(int,input().split()))
    c[n] = temp[0]
    a[n] = temp[1:M+1]


ans = 10**7

for i in range(2 ** N):
    price = 0
    intelligence = [0 for _ in range(M)]
    for j in range(N):
        if ((i >> j) & 1):
            price += c[j]
            for k in range(M):
                intelligence[k] += a[j][k]
    flag = 1
    for k in range(M):
        if intelligence[k] < X:
            flag = 0
    if flag == 1:
        ans = min(ans,price)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ca = [0]*n
for i in range(n):
    ca[i] = list(map(int,input().split()))
ans = 10**10
for i in range(2**n):
    s = [0]*m
    c = 0
    for j in range(n):
        if (i>>j)&1:
            c += ca[j][0]
            for k in range(1,m+1):
                s[k-1] += ca[j][k]
    s = sorted(s)
    if s[0] >= x:
        ans = min(ans,c)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = []
A = []
Min = 9999999999
for i in range(n):
    a = list(map(int,input().split()))
    c.append(a[0])
    A.append(a[1:])
for i in range(2**n):
    lists = []
    m_list = [0]*m
    cost = 0
    for j in range(n):
        if ((i >> j) & 1):
            lists.append(1)
        else:
            lists.append(0)
    for k in range(len(lists)):
        if lists[k] == 1:
            cost += c[k]
            for s in range(m):
                m_list[s] += A[k][s]
        else:
            pass
    cnt = 0
    for h in range(m):
        if m_list[h] >= x:
            cnt += 1
    if cnt >= m:
        Min = min(Min,cost)
if Min == 9999999999:
    print(-1)
else:
    print(Min)

Submission status: Accepted

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

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

res = float('inf')
for i in range(1<<N):
  scores = [0] * M
  cost = 0
  for j in range(N):
    if (i>>j)&1:
      for k,p in enumerate(books[j][1:]):
        scores[k] += p
      cost += books[j][0]

  if all([ score >= X for score in scores]):
    res = min(res, cost)

print(res) if res < float('inf') else print('-1')

Submission status: Accepted

Solution code:
import itertools

INF = 10**18

N, M, X = map(int, input().split())
C = [0]*N
A = [[] for i in range(N)]
for i in range(N):
    src = list(map(int, input().split()))
    C[i] = src[0]
    A[i] = src[1:]
ans = INF
for ptn in itertools.product([0,1], repeat=N):
    point = [0]*M
    m = 0
    for j in range(N):
        if ptn[j]:
            m += C[j]
            for ii, a in enumerate(A[j]):
                point[ii] += a
    ok = True
    for j in range(M):
        if point[j] < X:
            ok = False
            break
    if ok:
        ans = min(ans, m)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys

def calcSum(N, BuyingList_bool, Books):
    Price = 0
    for Num in range(N):
        if(BuyingList_bool[Num]):
            Price += Books[Num][0]
    return Price

def search(N, M, X, Books, BuyingList_bool, Prices = [], BranchPos =0):
    if(BranchPos == N):

        Complehensives = [0] * M
        for m in range(M):
            for n in range(N):
                if(BuyingList_bool[n]):
                    Complehensives[m] += Books[n][m+1]
            if(Complehensives[m] < X):
                return None

        Prices.append( calcSum(N, BuyingList_bool, Books) )
        return Prices
    BuyingList_bool[BranchPos] = True
    search(N, M, X, Books, BuyingList_bool, Prices, BranchPos+1)
    BuyingList_bool[BranchPos] = False
    search(N, M, X, Books, BuyingList_bool, Prices, BranchPos+1)
    return Prices



if(__name__ == '__main__'):
    NMX = input().split()

    N= int(NMX[0].strip())
    M= int(NMX[1].strip())
    X= int(NMX[2].strip())

    Books = []
    AllSum = []
    for Num in range(M+1):
        AllSum.append(0) # [M] -> value
    for Num in range(N):
        List = []
        In = input().split()
        for Str in In:
            List.append(int(Str.strip()))
        Books.append(List)

    BuyingList_bool = [True] * N
    Prices = search(N, M, X, Books, BuyingList_bool)
    if(len(Prices) ==0):
        print(-1)
    else:
        print( min(Prices) )

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
list = []
skill=[0]*M
ans = -1
for i in range(N):
    item = input().split()
    list.append(item)
for i in range(2**N):
    skill = [0]*M
    sum = 0
    for j in range(N):
        if ((i >>j) & 1):
            for u in range(M):
                skill[u]+= int(list[j][u+1])
            sum += int(list[j][0])
    if min(skill)>=X:
        if ans == -1:
            ans =sum
        else:
            ans = min(ans,sum)
print(ans)

Submission status: Accepted

Solution code:

def main():
    N, M, X = map(int, input().split())
    C = []
    A = []
    for n in range(N):
        ls = list(map(int, input().split()))
        C.append(ls[0])
        A.append(ls[1:])

    result = -1
    for i in range(1 << N):
        t = [0] * M
        c = 0
        for j in range(N):
            if i & (1 << j):
                c += C[j]
                for k in range(M):
                    t[k] += A[j][k]

            if all(x >= X for x in t):
                if result == -1:
                    result = c
                else:
                    result = min(result, c)

    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# a = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S=[[0 for j in range(M+1)] for i in range(N)]
for i in range (N):
    S[i]=list(map(int,input().split()))


skill=[0]*(M)

ans=10000000




for i in range(2 **N):
    skill=[0]*M
    cost=0
    for j in range(N):
        if ((i >> j) & 1):
            #print(i,j)
            for k in range(1,M+1):
                skill[k-1]+=S[j][k]
                
            cost+=S[j][0]    
            #print(cost)
            #print(skill)
    for j in range(M):
        if skill[j]<X:
            break
        if j==M-1:
            if ans>cost:
                ans=cost
                
    
if ans==10000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

#ca = [map(int, input().split()) for _ in range(n)]
#ca = [input().split() for l in range(n)]
import sys
ca = [[int(c) for c in l.split()] for l in sys.stdin]
#c, a = [list(i) for i in zip(*ca)]
#print(ca)
#print(ca[0][0])
c=[]
for l in range(n):
    c.append(ca[l][0])
#print(c)

for l in range(n):
    del ca[l][0]
#print(ca)

INF = float('INF')
min_cost = INF
 
def dfs(i, cost, learn):
    if i == n:
        if min(learn) >= x:
            return cost
        else:
            return INF
    else:
        new_learn = [X + Y for (X, Y) in zip(ca[i], learn)]
        cost = min(dfs(i + 1, cost, learn), dfs(i + 1, cost + c[i], new_learn))
        return cost
 
min_cost = dfs(0, 0, [0] * m)
 
if min_cost == INF:
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
# Nについての全探索でいけそう
n, m, x = map(int, input().split())
cost, A = [0] * n, [[]] * n
for i in range(n):
    line = list(map(int, input().split()))
    cost[i] = line[0]
    A[i] = line[1:]

ans = 10**10

for bit in range(1 << n):
    tmp_cost = 0
    tmp_a = [0] * m
    for i in range(n):
        if bit >> i & 1 == 1:
            tmp_cost += cost[i]
            for j in range(m):
                tmp_a[j] += A[i][j]
        # すべてXを越えてるかチェック filterがどこにあるかわからんw
    if len(list(filter(lambda t: t >= x, tmp_a))) == m:
        ans = min(ans, tmp_cost)
print(ans if ans != 10**10 else -1)

Submission status: Accepted

Solution code:
import itertools
from operator import add

def li():
    return list(map(int, input().split()))
def mi():
    return map(int, input().split())
def ii():
    return int(input())
def lim(N):
    return [int(input()) for i in range(N)]

N, M, X = mi()
C = []
A = []
for i in range(N):
    CA = li()
    C.append(CA[0])
    A.append(CA[1:])

Cost = 10 ** 8
for i in range(1, N + 1):
    # 組み合わせを作成する。
    it = itertools.combinations(range(N) ,i)

    # 組み合わせに対しての理解度を合計し、それぞれMを超えているのかを確認する。
    for i in it:
        rikaido = [0] * M
        cur_cost = 0
        for j in i:
            rikaido = list(map(add, rikaido, A[j]))
            cur_cost += C[j]

            rikaiflag = True
            for k in range(M):
                if rikaido[k] < X:
                    rikaiflag = False
                    break
            if rikaiflag:
                Cost = min(Cost,cur_cost)

if Cost == 10 ** 8:
    print(-1)
else:
    print(Cost)

Submission status: Accepted

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

ans = 10**8
for i in range(2**N):
    cnt = 0
    temp = [0]*M
    for j in range(N):
        if i & (1<<j) == 0:
            continue
        for k in range(M):
            temp[k] += L[j][k+1]
        cnt += L[j][0]
    f = True
    for k in range(M):
        if temp[k] < X:
            f = False
            break
    if f:
        ans = min(ans, cnt)

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

Submission status: Accepted

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

search = []
costs = []

for i in range(2 ** N):
    B = []
    for j in range(N):
        if ((i >> j) & 1):
            B.append(j)
    search.append(B)

for i in search:
    sum = [0 for t in range(M)]
    for k in range(M):
        for j in i:
            sum[k] += int(U[j][k + 1])

    if min(sum) >= X:
        cost = 0
        for l in i:
            cost += int(U[l][0])
        costs.append(cost)

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

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)

ans = 10**8
for b in range(2**N):
    A_sum = np.zeros(A[0].shape,dtype=np.int32)
    for i in range(N):
        if (b >> i) % 2 == 1:
            A_sum += A[i]
    for i in range(1,M+1):
        if A_sum[i] < X:
            break
    else:
        ans = min(ans,A_sum[0])

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

Submission status: Accepted

Solution code:
def judge(A,M,X):
    flag = True
    for i in range(M):
        if A[i] < X:
            flag = False
            break
    return flag

if __name__ == "__main__":
    N,M,X = map(int,input().split())
    books = []
    b_comb = []
    
    for i in range(N):
        books.append([int(x) for x in input().split()])

    for i in range(2**N):
        skill = [0 for i in range(M)]
        cost = 0
        for j in range(N):
            if ((i >> j) & 1):
                cost += books[j][0]
                for k in range(1, M+1):
                    skill[k-1] += books[j][k]
        if judge(skill,M,X):
            b_comb.append(cost)

    if len(b_comb) != 0:
        print(min(b_comb))
    else:
        print('-1')

Submission status: Accepted

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

# 合否判定のためのフラグ
Flag = False
cost_min = 0
for i in range(n):
  cost_min += cas[i][0]

# 全ての組み合わせについてチェック
for i in range(2**n):
  bag  = [0]*(m+1)
  # バッグに荷物を詰める
  for j in range(n):
    if ((i>>j) & 1):
      for k in range(m+1):
        bag[k] += cas[j][k]
  # 条件を満たしているか調べる
  if (min(bag[1:]) >= x):
    Flag = True
    cost_min = min(cost_min, bag[0])

if (Flag):
  print(cost_min)
else:
  print(-1)

Submission status: Accepted

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


cmin=12*10**5+1
for bit in range(2**N):
    A=[0]*M
    c=0
    for j in range(N):
        if (bit>>j)&1:
            c+=l[j][0]
            A=[x+y for (x,y) in zip(A, l[j][1:])]
    if min(A) >= X:
        cmin=min(cmin,c)

if cmin!=12*10**5+1:
    print(cmin)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
a = [list(map(int, input().split())) for i in range(N)]
b = ["0" * (N - len(format(i, "b"))) + format(i, "b") for i in range(2 ** N)]
c = []

for i in b:
    d = []
    for j in range(M + 1):
        e = 0
        for k in range(N):
            e += a[k][j] * int(i[k])
        d.append(e)
    if min(d[1:]) >= X:
        c.append(d[0])
if c:
    print(min(c))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

for _ in range(n):
    l.append(list(map(int,input().split())))
    
ans=10**8
for i in range(1<<n):
    p=0
    u=[0] * m

    for j in range(n):
        if(i>>j)&1:
            p+=l[j][0]

            for io in range(m):
                u[io] += l[j][1+io]

        f=0
        for jo in range(m):
            if u[jo] < x: f=1 ; break

        if not f:
            ans=min(ans,p)

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

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m,x=f()
lc,ll=[],[]
for _ in range(n): c,*l=f(); lc+=[c]; ll+=[l]
a=10**9
for i in range(2**n):
  lm,t=[0]*m,0
  for j in range(n):
    if i>>j&1:
      for k in range(m): lm[k]+=ll[j][k]
      t+=lc[j]
  if all(s>=x for s in lm): a=min(a,t)
print([-1,a][a<10**9])

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for i in range(N)]
costs=[]
for bit in range(1<<N):
    cost=0
    understand=[0]*M
    for digit in range(N):
        if (bit>>digit)&1:
            cost+=CA[digit][0]
            for m in range(M):
                understand[m]+=CA[digit][m+1]
    if all(understand[m]>=X for m in range(M)):
        costs.append(cost)
print(min(costs) if costs else -1)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for i in range(N)]
min_cost=float("inf")
for bit in range(1<<N):
    cost=0
    understand=[0]*M
    for digit in range(N):
        if (bit>>digit)&1:
            cost+=CA[digit][0]
            for m in range(M):
                understand[m]+=CA[digit][m+1]
    if all(understand[m]>=X for m in range(M)):
        min_cost=min(min_cost,cost)
print(min_cost if min_cost!=float("inf") else -1)

Submission status: Accepted

Solution code:
import numpy as np

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

ca = []
for _ in range(N):
  ca.append( list(map(int, input().split())))
ca.sort(key=lambda x:x[0])
ca = np.array(ca)
#
ans = 10000000
skill = [0]*(M+1)


def DFS(n):
  global ans,skill
  if skill[0] >= ans:
    return
  if min(skill[1:]) >= X:
    ans = min(ans, skill[0])
    return
  if n >= N:
    return
  skill = skill + ca[n]
  DFS(n+1)
  skill = skill - ca[n]
  DFS(n+1)
  return
#

DFS(0)
if ans == 10000000:
  print(-1)
else:
  print(ans)
#

Submission status: Accepted

Solution code:
import numpy as np

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

ca = []
for _ in range(N):
  ca.append( list(map(int, input().split())))
ca.sort(key=lambda x:-x[0])
ca = np.array(ca)
#
ans = 10000000
skill = [0]*(M+1)


def DFS(n):
  global ans,skill
  if skill[0] >= ans:
    return
  if min(skill[1:]) >= X:
    ans = min(ans, skill[0])
    return
  if n >= N:
    return
  DFS(n+1)
  skill = skill + ca[n]
  DFS(n+1)
  skill = skill - ca[n]
  return
#

DFS(0)
if ans == 10000000:
  print(-1)
else:
  print(ans)
#

Submission status: Accepted

Solution code:
import numpy as np

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

ca = []
for _ in range(N):
  ca.append( list(map(int, input().split())))
ca.sort(key=lambda x:-x[0])
ca = np.array(ca)
#
ans = 10000000
skill = [0]*(M+1)


def DFS(n,skill):
  global ans
  if skill[0] >= ans:
    return
  if min(skill[1:]) >= X:
    ans = min(ans, skill[0])
    return
  if n >= N:
    return
  DFS(n+1,skill)
  skill = skill + ca[n]
  DFS(n+1,skill)
  skill = skill - ca[n]
  return
#

DFS(0,skill)
if ans == 10000000:
  print(-1)
else:
  print(ans)
#

Submission status: Accepted

Solution code:
import numpy as np

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

ca = []
for _ in range(N):
  ca.append( list(map(int, input().split())))
ca.sort(key=lambda x:-x[0])
ca = np.array(ca)
#
ans = 10000000
skill = [0]*(M+1)


def DFS(n,skill):
  global ans
  if skill[0] >= ans:
    return
  if min(skill[1:]) >= X:
    ans = min(ans, skill[0])
    return
  if n >= N:
    return
  s = skill.copy()
  DFS(n+1,s)
  s = s + ca[n]
  DFS(n+1,s)
  return
#

DFS(0,skill)
if ans == 10000000:
  print(-1)
else:
  print(ans)
#

Submission status: Accepted

Solution code:
import numpy as np

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

ca = []
for _ in range(N):
  ca.append( list(map(int, input().split())))
ca.sort(key=lambda x:-x[0])
ca = np.array(ca)
#
ans = 10000000
skill = [0]*(M+1)


def DFS(n,skill):
  global ans
  if skill[0] >= ans:
    return
  if min(skill[1:]) >= X:
    ans = min(ans, skill[0])
  if n >= N:
    return
  s = skill.copy()
  DFS(n+1,s)
  s = s + ca[n]
  DFS(n+1,s)
  return
#

DFS(0,skill)
if ans == 10000000:
  print(-1)
else:
  print(ans)
#

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

ca = []
for _ in range(N):
  ca.append( list(map(int, input().split())))
ca = np.array(ca)
#print(ca)
ans = 10000000

b = [0,1]
for p in list(itertools.product(b, repeat=N)): 
  a = np.array(p)
  to = a@ca
  if min(to[1:]) >= X:
    ans = min(ans, to[0])
#
if ans == 10000000:
  print(-1)
else:
  print(ans)
#

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m,x=f()
lc,ll=[],[]
for _ in range(n):
  c,*l=f()
  lc.append(c)
  ll.append(l)
a=10**9
for i in range(2**n):
  lm=[0]*m
  t=0
  for j in range(n):
    if i>>j&1:
      for k in range(m):
        lm[k]+=ll[j][k]
      t+=lc[j]
  if all(s>=x for s in lm):
    a=min(a,t)
print(a if a<10**9 else -1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = [[int(i) for i in input().split(" ")] for j in range(n)]
mi = 10**7

for i in range(1, 2**n):
    te = [0]*m
    bi = bin(i+2**n)[3:]
    c = 0
    for j in range(n):
        if bi[j] == "0":
            continue
        te = [x+y for x, y in zip(te, a[j][1:])]
        c += a[j][0]
    if sum([1 for i in te if i >= x]) == m:
        mi = min(mi, c)
if mi == 10**7:
    print(-1)
else:
    print(mi)

Submission status: Accepted

Solution code:
def nextg(x, place):
    if x[place] == 1:
        x[place] = 0
        if place == 0:
            return x
        return nextg(x, place-1)
    if x[place] == 0:
        x[place] = 1
        return x
n, m, t = map(int,input().split())
generator = [0]*n
books = []
for i in range(0, n):
    books.append(list(map(int,input().split())))
min = 0
for i in range(0, n):
    min+=books[i][0]
flag = 0
for i in range(0, pow(2,n)):
    found = False
    for k in range(1, m+1):
        sum = 0
        for j in range(0, n):
            sum+=books[j][k]*generator[j]
        if sum<t:
            break
        elif k == m:
            found = True
            flag = 1         
    cost = 0
    for p in range(0, n):
        cost+=books[p][0]*generator[p]
    if found == True and cost<min:
        min = cost
    generator = nextg(generator, n-1)
if flag == 1:
    print(min)
else:
    print(-1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m,x = LI()
    aa = [LI() for _ in range(n)]

    ii = [2**i for i in range(n)]
    r = inf
    for i in range(1,2**n):
        t = [0] * m
        tr = 0
        for j in range(n):
            if i & ii[j] > 0:
                tr += aa[j][0]
                for k in range(m):
                    t[k] += aa[j][k+1]
        if all(c >= x for c in t):
            if r > tr:
                r = tr
    if r == inf:
        return -1

    return r

print(main())

Submission status: Accepted

Solution code:
n,m,x=map(int, input().split())
zen=[]
for y in range(2**n):
    zen.append(y)
book=[]
for y in range(n):
    a=list(map(int, input().split()))
    book.append(a)
kakaku=0
kakakum=10**7
skill=[0]*m
for y in zen:
    for z in range(n):
        if ((y>>z)&1):
            kakaku+=book[z][0]
            for aa in range(m):
                skill[aa]+=book[z][aa+1]
    skill.sort()
    if skill[0]>=x:
        if kakakum>kakaku:
            kakakum=kakaku
    skill=[0]*m
    kakaku=0
if kakakum==10**7:
    kakakum=-1
print(kakakum)

Submission status: Accepted

Solution code:
n_book, n_algo, target = map(int,input().split())
cost_ls = [0] * n_book
up_ls = [0] * n_book
for i in range(n_book):
    ls = list(map(int, input().split()))
    cost_ls[i] = ls[0]
    up_ls[i] = ls[1:]

n_pattern = 2 ** n_book
min_cost = float('inf')
for pattern in range(n_pattern):
    cost = 0
    score_ls = [0] * n_algo
    can = True
    for ind_book in range(n_book):
        if (pattern >> ind_book) & 1:
            cost += cost_ls[ind_book]
            for ind_algo in range(n_algo):
                score_ls[ind_algo] += up_ls[ind_book][ind_algo]
    for ind_algo in range(n_algo):
        if score_ls[ind_algo] < target:
            can = False
    if can:
        min_cost = min(min_cost, cost)
if min_cost == float('inf'):
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
from itertools import product
N,M,X = map(int,input().split())
C = []
A = []
for n in range(N):
    a = list(map(int,input().split()))
    C.append(a[0])
    A.append(a[1:])
INF = 10**9
ans = INF
for p in product([0,1], repeat=N):
    sm = [0] * M
    cost = 0
    for i in range(N):
        if p[i]: # bitが立っていたら
            for m in range(M):
                sm[m] += A[i][m]
            
            cost += C[i] 
    #print (p,sm)
    if min(sm) >= X:
        ans = min(ans,cost)
if ans==INF: # 更新されていなければ-1を出力
    print (-1)
else:
    print (ans)

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 a in range(m+1):
        s[a] += k[a]
    if min(s[1:]) >= x:
      ans = min(ans, s[0])
if ans == 10**9:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

ans = 1e9

for mask in range(2**n):
	cost = 0
	cnt = [0 for _ in range(m)]
	for i in range(n):
		if ( (1 << i) & mask ) == 0:
			continue
		cost += c[i]
		for j in range(m):
			cnt[j] += ara[i][j]
	if min(cnt) >= x:
		ans = min(ans, cost)

if ans == 1e9:
	ans = -1

print(ans)

Submission status: Accepted

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

ans = 1e9

for mask in range(2**n):
	cost = 0
	cnt = [0 for _ in range(m)]
	for i in range(n):
		if ( (1 << i) & mask ) == 0:
			continue
		cost += c[i]
		for j in range(m):
			cnt[j] += ara[i][j]
	ok = 1
	for i in range(m):
		if cnt[i] < x:
			ok = 0
	if ok:
		ans = min(ans, cost)

if ans == 1e9:
	ans = -1

print(ans)

Submission status: Accepted

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

ans = 1e9

for mask in range(2**15):
	cost = 0
	cnt = [0 for _ in range(m)]
	for i in range(n):
		if ( (1 << i) & mask ) == 0:
			continue
		cost += c[i]
		for j in range(m):
			cnt[j] += ara[i][j]
	ok = 1
	for i in range(m):
		if cnt[i] < x:
			ok = 0
	if ok:
		ans = min(ans, cost)

if ans == 1e9:
	ans = -1

print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [0] * n
a = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    c[i] = tmp[0]
    a[i] = tmp[1:]
ans_flag = False
ans = sum(c)
for i in range(1 << n):
    flag = [False] * n
    for j in range(n):
        if (i >> j) & 1:
            flag[j] = True
    ok = [0] * m
    cost = 0
    for k in range(n):
        if flag[k]:
            for t in range(m):
                ok[t] += a[k][t]
            cost += c[k]
        look = [False] * m
        for s in range(m):
            if ok[s] >= x:
                look[s] = True
            if all(look):
                ans = min(ans, cost)
                ans_flag = True
if ans_flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

ans = float('inf')

for i in range(2**n):#行数回す。(１０進数)
    hold = [0] * (m+1)
    for j in range(n):#行数回す（２進数）。flagを立てる。
        if (i >> j) & 1:#　i(二進数)をj個右に動かす。
            for k in range(m+1):
                hold[k] += c[j][k]
    if min(hold[1:]) >= x : 
        ans = min(ans,hold[0])

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [0] * n
a = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    c[i] = tmp[0]
    a[i] = tmp[1:]
ans_flag = False
ans = sum(c)
for i in range(1 << n):
    flag = [False] * n
    for j in range(n):
        if (i >> j) & 1:
            flag[j] = True
    ok = [0] * m
    cost = 0
    for k in range(n):
        for t in range(m):
            if flag[k]:
                ok[t] += a[k][t]
        if flag[k]:
            cost += c[k]
        look = [False] * m
        for s in range(m):
            if ok[s] >= x:
                look[s] = True
            if all(look):
                ans = min(ans, cost)
                ans_flag = True
if ans_flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

import numpy as np
nmx = input().split(" ")
n = int(nmx[0])
m = int(nmx[1])
x = int(nmx[2])
a = []
c = []
total = []
pattern = [[0] * n]

for i in range(pow(2, n) - 1):
  pattern.append([pattern[i][j] for j in range(n)])
  for j in range(n):
    if pattern[i+1][j] == 0:
      pattern[i+1][j] = 1
      break
    else:
      pattern[i+1][j] = 0

r = 0

for i in range(n):
  text = input().split(" ")
  c.append(int(text[0]))
  a.append([int(text[i]) for i in range(1, m + 1)])

a = np.array(a)

for i in range(pow(2, n) - 1, -1,  -1):
  array = a.T @ pattern[i]
  if not(all(v >= x for v in array)):
    pattern = np.delete(pattern, i, 0)


total = [np.dot(np.array(c), p) for p in pattern]
# print(pattern)
# print(total)

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