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:
#
# abc167 c
#
import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)


def resolve_bit():
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split())) for _ in range(N)]

    ans = float("inf")
    for bit in range(1 << N):
        S = [0]*(M+1)
        for i, ca in enumerate(CA):
            if (1 << i) & bit == 1 << i:
                S = list(map(sum, zip(S, ca)))
        for s in S[1:]:
            if s < X:
                break
        else:
            ans = min(ans, S[0])

    if ans == float("inf"):
        ans = -1

    print(ans)


def resolve():
    global N, M, X, CA
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split())) for _ in range(N)]

    b = deque()
    ans = dfs(0, b)
    if ans == float("inf"):
        ans = -1

    print(ans)


def dfs(n, B):
    if n == N:
        S = [0]*(M+1)
        for i, ca in enumerate(CA, 1):
            if i in B:
                S = list(map(sum, zip(S, ca)))
        if min(S[1:]) < X:
            return float("inf")
        else:
            return S[0]

    ans = float("inf")
    B.append(n+1)
    ans = min(ans, dfs(n+1, B))
    B.pop()
    ans = min(ans, dfs(n+1, B))

    return ans


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
# author:  Taichicchi
# created: 14.09.2020 22:23:14

import sys
from itertools import combinations

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

C = []
A = []

for i in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)
comb = [0, 1, 2]

save = []

for choice in range(1, N + 1):
    for comb in combinations(list(range(N)), choice):
        ls = [0 for _ in range(M)]
        for i in comb:
            for m in range(M):
                ls[m] += A[i][m]
            if all(list(map(lambda x: x >= X, ls))):
                save.append(sum([C[_] for _ in comb]))
if save:
    print(min(save))
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

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

ans = float('inf')
for bit in range(1<<n):
  cost = 0
  skill = [0]*m
  for i in range(n):
    if bit & 1<<i:
      cost += c[i]
      for j in range(m):
        skill[j] += a[i][j]
  if min(skill) >= x:
    ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ca=[]
ans=10**9
for i in range(n):
  tmp=list(map(int,input().split()))
  ca.append(tmp)
for p in range(2**n):
  i_bin = (bin(p)[2:]).zfill(n)
  fl=1
  for i in range(1,m+1):
    ttl=sum([int(i_bin[k])*ca[k][i] for k in range(n)])
    if ttl<x: fl=0
  ansc=sum([int(i_bin[k])*ca[k][0] for k in range(n)])
  if fl and ansc<ans:
    ans=ansc
if ans==10**9: print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

class Solver:
    def __init__(self, N, M, X, C, A):
        self.N = N
        self.M = M
        self.X = X
        self.C = C
        self.A = A

    def is_achievable(self, A):
        result = [0] * self.M
        for a_row in A:
            for i, a in enumerate(a_row):
                result[i] += a

        for n in result:
            if n < self.X:
                return False
        return True

    def solve(self):
        if not self.is_achievable(self.A):
            print(-1)
            return

        min_cost = 10 ** 10
        index_C = [ i for i in range(N) ]
        for i in range(len(index_C)+1):
            for comb in combinations(index_C, i):
                cur_A = []
                cur_cost = 0
                for i in comb:
                    cur_A.append(self.A[i])
                    cur_cost += C[i]
                if self.is_achievable(cur_A):
                    min_cost = min(min_cost, cur_cost)

        print(min_cost)

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

C = [0] * N
A = []

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

solver = Solver(N, M, X, C, A)
solver.solve()

Submission status: Accepted

Solution code:
from itertools import combinations

def is_achievable(M, X, A):
    result = [0] * M
    for a_row in A:
        for i, a in enumerate(a_row):
            result[i] += a

    for n in result:
        if n < X:
            return False
    return True

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

    C = [0] * N
    A = []

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

    if not is_achievable(M, X, A):
        print(-1)
        return
    
    index_C = [ i for i in range(N) ]
    min_cost = 10 ** 10
    for i in range(len(index_C)+1):
        for comb in combinations(index_C, i):
            cur_A = []
            cur_cost = 0
            for i in comb:
                cur_A.append(A[i])
                cur_cost += C[i]
            if is_achievable(M, X, cur_A):
                min_cost = min(min_cost, cur_cost)

    print(min_cost)

main()

Submission status: Accepted

Solution code:
N , M , X = list(map(int, input().split()))
C = []
for _ in range(N):
    C.append(list(map(int, input().split())))
ans = 10**9
for i in range(2**N):
    i_bin = (bin(i)[2:]).zfill(N)
    flag = True
    for j in range(1,M+1):
        tot = sum([ int(i_bin[k])* C[k][j] for k in range(N)])
        if tot < X:
            flag = False
    am = sum([ int(i_bin[k]) * C[k][0] for k in range(N)])
    if flag and am<ans:
        ans = am

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

Submission status: Accepted

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


def num2bi(num):
    l = [0] * N
    for i in range(N):
        if num >= 2 ** (N - 1 - i):
            num -= 2 ** (N - 1 - i)
            l[i] = 1
    return l


SUM = [0] * M
A = [[0] * M for _ in range(N)]
C = []
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(M):
        SUM[j] += a[j + 1]
        A[i][j] = a[j + 1]
    C.append(a[0])

ans = sum(C)
if min(SUM) < X:
    ans = -1
else:
    for num in range(2 ** N):
        SUM = [0] * M
        tmp = 0
        for i in range(N):
            if num2bi(num)[i] == 1:
                for j in range(M):
                    SUM[j] += A[i][j]
                tmp += C[i]
        if min(SUM) >= X:
            ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
[N, M, X] = [int(i) for i in input().split()]
bk = [[int(i) for i in input().split()] for _ in range(N)]

ans = 12*10**5 + 1
for seq in product(range(2), repeat=N):
    S = [0]*(M+1)
    for i in range(N):
       for j in range(M+1):
           S[j] += seq[i]*bk[i][j]     
    if min(S[1:M+1]) >= X:
        ans = min(ans, S[0])

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
INF = 10000000000000
N,M,X = map(int,input().split())

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

ans = INF

for bit in range(1 << N):
    sum = 0
    skill = [0] * M
    for n in range(N):
        if bit & (1 << n):
            for i, s in enumerate(A[n],0):
                skill[i] += s
            sum += C[n]

    flag = True
    for i in range(M):
        if skill[i] < X:
            flag = False
            break
    if flag:
        ans = min(ans,sum)

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

Submission status: Accepted

Solution code:
#
# abc167 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)


def resolve():
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split())) for _ in range(N)]

    ans = float("inf")
    for bit in range(1 << N):
        S = [0]*(M+1)
        for i, ca in enumerate(CA):
            if (1 << i) & bit == 1 << i:
                S = list(map(sum, zip(S, ca)))
        for s in S[1:]:
            if s < X:
                break
        else:
            ans = min(ans, S[0])

    if ans == float("inf"):
        ans = -1

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

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

d = []

for i in range(1 << N):
    s = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1:
            # print(j, "entry")
            for k in range(M):
                s[k] += a[j][k+1]
            c += a[j][0]

    # print(s, c, d)

    b = True
    for ii in s:
        if ii < X:
            b = False
    if b:
        d.append(c)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(n)]
ans = []
#n冊の本において買うか買わないかの2通りなので2**n
for i in range(2**n):
    #リストの中身は値段1と理解度m個
    a = [0]*m
    price = 0
    for j in range(n):
        #n冊あるうちj冊目を買うか買わないかを判定
        if ((i >> j) & 1):
            for k in range(m):
                a[k] += c[j][k+1]
            #j冊めを買うので、合計金額を増やす
            price += c[j][0]
    if all(j >= x for j in a):
        ans.append(price)

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
def main():
    n, m, x = map(int, input().split())
    data = np.array(read().split(), np.int64)
    data = data.reshape(n, -1) # dataをn行に整形
    cost_per_cost = data[:, 0] # data全行の0列
    effect_per_book = data[:, 1:]

    costs = np.zeros(2**n, np.int64)
    # ability 行数：2**n(本の組み合わせパターン), 列数：アルゴリズムの数
    ability = np.zeros((2**n, m), np.int64)
    for i in range(n):
        costs[1<<i:1<<(i+1)] = costs[:1<<i] + cost_per_cost[i]
        ability[1<<i:1<<(i+1)] = ability[:1<<i] + effect_per_book[i]
    ok = np.all(ability >= x, axis=1)
    res = costs[ok]
    if len(res) == 0:
        print(-1)
    else:
        print(res.min())

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#import numpy as np
from itertools import product
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        books.append(tuple(map(int, input().split())))
    p = tuple(product((0, 1), repeat=n))
    r = float('inf')
    for pe in p:
        effects = [0] * (m + 1)
        for i1 in range(n):
            if pe[i1]:
                for i2 in range(m+1):
                    effects[i2] += books[i1][i2]
        if all([e >= x for e in effects[1:]]):
            r = min(r, effects[0])
    if r == float('inf'):
        print(-1)
    else:
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = list(list(map(int,input().split())) for _ in range(n))
ans = 10**7
for i in range(1<<n):
    mokuhyo = [0]*m
    cost = 0
    for j in range(n):
        if i>>j&1:
            for r in range(m):
                mokuhyo[r] += c[j][r+1]
            cost += c[j][0]
    if all(k>=x for k in mokuhyo):
        ans = min(ans, cost)
print("-1" if ans == 10**7 else ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(n)]
ans = []
#n冊の本において買うか買わないかの2通りなので2**n
for i in range(2**n):
    #リストの中身は値段1と理解度m個
    a = [0]*(m+1)
    com = i
    for j in range(n):
        if com >= (2**(n-j-1)):
            com -= 2**(n-j-1)
            for k in range(m+1):
                a[k] += c[j][k]
    price = a[0]
    del a[0]
    if all(a[j]>=x for j in range(m)):
        #print(price)
        ans.append(price)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
prices = []
for i in range(2**n):
  buy = [[] for _ in range(m+1)]
  for j in range(n):
    if ((i >> j) & 1):
      for k in range(m+1):
        buy[k].append(c[j][k])
  for k in range(1,m+1):
    if sum(buy[k]) < x:
      break
  else:
    prices.append(sum(buy[0]))
if len(prices) == 0:
  print(-1)
else:
  print(min(prices))

Submission status: Accepted

Solution code:
import numpy as np

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

cost = float("inf")
for i in range(2**N):
  tmp = np.array([0 for _ in range(M+1)])
  for j in range(N):
    if (i>>j) & 1:
      tmp += np.array(C[j])
  if min(tmp[1:]) >= X:
    cost = min(cost, tmp[0])

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

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
books = []
for i in range(n):
  ins = list(map(int, input().split()))
  books.append({"c": ins[0], "a": ins[1: m+1]})
ans = float('inf')
for i in range(1, n+1):
  book_list = list(itertools.combinations(list(range(n)), i))
  for lis in book_list:
    cost_sum = 0
    a_sum = [0] * m
    ok = 0
    ok_list = [False] * m
    for j in lis:
      cost_sum += books[j]['c']
      for k in range(m):
        a_sum[k] += books[j]['a'][k]
        if not ok_list[k] and a_sum[k] >= x:
          ok += 1
          ok_list[k] = True
    if ok == m and ans > cost_sum:
      ans = cost_sum
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

li=[]
ans=100000000000000000000000000000000

for j in range(N):
    a=list(map(int,input().split()))
    li.append(a)

for k in range(2**N):
    temp=0
    skill=[0]*M
    k=str(bin(k))
    k=k[2:]
    while len(k)!=N:
        k="0"+k
    for l in range(N):
        if k[l]=="1":
            temp+=li[l][0]
            for m in range(1,M+1):
                skill[m-1]+=li[l][m]
    if min(skill)>=X:
        if ans>temp:
            ans=temp
if ans==100000000000000000000000000000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
[N, M, X] = map(int, list(input().split(' ')))
A = []
C = []
for i in range(N):
    c, *a = map(int, input().split(' '))
    C.append(c)
    A.append(a)
#print(C)
#print(A)

INF = 10**10
min_cost = INF

for b in range(2**N): 
    # これがバイナリーベースの全探索となる。今回のキモ part 1
    # 一つのループが本の購入セットに対応している
    # 各ビットがそれぞれの本を購入するかどうか表している
    # 因みに b は bit を表しているつもり
    cost = 0 # この購入セットで使う金額
    algo_level = [0] * M # 各アルゴリズムトピックの理解度
    for i in range(N): 
        # これが各本のコストと理解度取得のためのループ
        # i 番目の本に対してループを回していく
        if(b >> i & 1): # この行が今回のキモ part 2。
            # i 番目の本の購入有無を判定するために、ビットシフトした値に対して '1 = 0b1' (つまり単なる (2進数の) 1) との論理積を求めている
            # この if 文が True であるということは、i 番目の本を買ったということ
            cost += C[i]
            for a in range(M): # (各本にある) 各アルゴリズムに対するループ
                algo_level[a] += A[i][a]
    if(min(algo_level) >= X): # 全てのアルゴリズムトピックが X 以上の理解度である場合…
        min_cost = min(cost, min_cost)

if(min_cost < INF):
    print(min_cost)
else:
    print('-1')

Submission status: Accepted

Solution code:
N, M, X = [int(_) for _ in input().split()]
A = []
C = []
for _ in range(N):
    c, *a = [int(_) for _ in input().split()]
    A.append(tuple(a))
    C.append(c)

ans = 10 ** 10
for i in range(2 ** N):
    v = [0 for _ in range(M)]
    c = 0
    for j in range(N):
        if i & 1 << j:
            for k, a in enumerate(A[j]):
                v[k] += a
            c += C[j]
    if min(v) >= X:
        ans = min(ans, c)

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

Submission status: Accepted

Solution code:
def main():
    n, m, x = map(int, input().split())
    book_list = [list(map(int, input().split())) for _ in range(n)]
    ans = 12 * 10 ** 5 + 1

    for i in range(2 ** n):
        money = 0
        level = [0] * m
        for j in range(n):
            if (i >> j) & 1:
                money += book_list[j][0]
                for k in range(m):
                    level[k] += book_list[j][k + 1]
        for j in range(m):
            if level[j] < x:
                break
        else:
            ans = min(ans, money)

    if ans == 12 * 10 ** 5 + 1:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split(' '))
A, C = [], []
for n in range(N):
  inp = list(map(int, input().split(' ')))
  C.append(inp[0])
  A.append(inp[1:])
  
def proceed_step(remained, current_cost, n):
  global N, X
  remained_next = []
  
  if not remained: return current_cost
  if n == N: return float('inf')
  
  for algorithm in remained:
    m, current_sum = algorithm[0], algorithm[1]
    current_sum += A[n][m]
    if current_sum < X:
      remained_next.append([m, current_sum])
      
  return min(proceed_step(remained, current_cost, n+1),
             proceed_step(remained_next, current_cost + C[n], n+1))

remained = [[m, 0] for m in range(M)]
total_cost = proceed_step(remained, current_cost=0, n=0)
if total_cost == float('inf'): print(-1)
else: print(total_cost)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 10 ** 5 * n
flag = False
for i in product([0,1], repeat=n):
    price = 0
    skill = [0] * m
    for index_, bit in enumerate(i):
        if bit:
            for j in range(m):
                skill[j] += book[index_][ j + 1]
            price += book[index_][0]
    if all(v >= x for v in skill):
        ans = min(ans, price)
        flag = True
if flag:
    print(ans)
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)]
d = []
for i in range(2**N):
    b = [0] * (M+1)
    e = i
    for j in range(N):
        if e >= (2**(N-j-1)) :
            e -= (2**(N-j-1))
            for k in range(M+1):
                b[k] += a[j][k]
    c = 1
    for j in range(1,M+1):
        if b[j] < X:
            c = 0
            break
    if c == 1:
        d.append(b[0])
if len(d) > 0:
    ans = min(d)
else:
    ans = -1
print(ans)

Submission status: Accepted

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

C = []
A = []

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

    C.append(q[0])
    A.append(q[1:])

#bit全探索

ans = 1300000

for bit in range(1 << N):
    acquire = [0] * M
    cost = 0
    for i in range(N):
        if (bit >> i) % 2 == 1:
            cost += C[i]
            acquire = [a + b for a, b in zip(acquire, A[i])]

    if min(acquire) >= X:
        ans = min(ans, cost)

if ans == 1300000:
    ans = -1

print(ans)

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 = -1
for i in range((1<<N)):
    u = [0] * M
    p = 0
    for j in range(N):
        if i & (1 << j):
            p += C[j]
            for k in range(M):
                u[k] += A[j][k]
    if min(u) >= X:
        if ans == -1 or ans > p:
            ans = p
print(ans)

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 = -1
for i in range((1<<N)):
    u = [0] * M
    p = 0
    for j in range(N):
        if i & (1 << j):
            p += C[j]
            for k in range(M):
                u[k] += A[j][k]
    if min(u) >= X:
        if ans == -1 or ans > p:
            ans = p
print(ans)

Submission status: Accepted

Solution code:
nb,na,level = map(int , input().split())
blevels = []
for i in range(nb):
    blevels.append(list(map(int , input().split())))
ans = float('inf')
#print(ans)
for i in range(1,2**nb):
    flag = 0
    levels_sum = [0]*na
    price_sum = 0
    for j in range(nb):
        if((1<<j) & i > 0):
            price_sum += blevels[j][0]
            for k in range(1,na+1):
                levels_sum[k-1] += blevels[j][k]
    #print(price_sum)
    #print(*levels_sum)
    for levels in levels_sum:
        if(levels < level):
         #   print("breaked")
            flag = 1
            break
    if(flag == 0 and ans > price_sum):
        ans = price_sum
        #print(ans)
if(ans != float('inf')):
    print(ans)
else:
    print("-1")

Submission status: Accepted

Solution code:
import itertools as it

N, M, X = map(int, input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
    # print(comb)
    bag = [0] * (M+1)
    for i in range(N):
        if comb[i] == 0:
            continue
        else:
            for j in range(M+1):
                bag[j] += book[i][j]

    if min(bag[1:]) < X:
        continue
    else:
        prices.append(bag[0])

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

Submission status: Accepted

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

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

# print(array)
# print(n)
ans = 10 ** 8
for i in range(2**n):

    skill = [0] * m
    price = 0
    count = 0
    for k in range(n):
        if (i >> k) & 1:

            price += array[k][0]
            for j in range(m):
                skill[j] += array[k][j+1]
    for l in range(m):
        if skill[l] < x:
            break
        else:
            count += 1
    if count == m:
        ans = min(ans, price)

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

Submission status: Accepted

Solution code:
import itertools as it

N,M,X=map(int,input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
	bag = [0] * (M+1)
	for i in range(N):
		if comb[i] == 0:
			continue
		else:
			for j in range(M+1):
				bag[j]+=book[i][j]
	if min(bag[1:]) < X:
		continue
	else:
		prices.append(bag[0])

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

Submission status: Accepted

Solution code:
import itertools as it
N, M, X = map(int, input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]
# print(f'book={book}')
combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
    # print(comb)
    bag = [0] * (M + 1)
    for i in range(N):
        if comb[i] == 0:
            continue
        else:
            for j in range(M + 1):
                bag[j] += book[i][j]
    # print(f'bag={bag}')
    if min(bag[1:]) < X:
        continue
    else:
        prices.append(bag[0])
if len(prices) == 0:
    print(-1)
else:
    print(min(prices))

Submission status: Accepted

Solution code:
import itertools as it

N,M,X=map(int,input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
	bag = [0] * (M+1)
	for i in range(N):
		if comb[i] == 0:
			continue
		else:
			for j in range(M+1):
				bag[j]+=book[i][j]
	if min(bag[1:]) < X:
		continue
	else:
		prices.append(bag[0])

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M, X = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    inf = 10**18

    # bit全探索
    # repeat=2だと(0,0), (0,1), (1,0), (1,1)になる
    ans = inf
    for i in product([0,1], repeat=N):
        ok = True
        for m in range(1, M + 1):
            s = 0
            for n in range(N):
                if i[n] == 1:
                    s += A[n][m]
            if s < X:
                ok = False
                break
        if ok:
            money = 0
            for n in range(N):
                if i[n] == 1:
                    money += A[n][0]
            ans = min(ans, money)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M, X = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    inf = 10**18

    # bit全探索
    # repeat=2だと(0,0), (0,1), (1,0), (1,1)になる
    ans = inf
    for i in product([0,1], repeat=N):
        ok = True
        for m in range(1, M + 1):
            s = 0
            for n in range(N):
                if i[n] == 1:
                    s += A[n][m]
            if s < X:
                ok = False
        if ok:
            money = 0
            for n in range(N):
                if i[n] == 1:
                    money += A[n][0]
            ans = min(ans, money)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M, X = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    for m in range(1, M + 1):
        s = 0
        for n in range(N):
            s += A[n][m]
        if s < X:
            print(-1)
            exit()

    # bit全探索
    # repeat=2だと(0,0), (0,1), (1,0), (1,1)になる
    ans = 10 ** 15
    for i in product([0,1], repeat=N):
        c = 0
        for m in range(1, M + 1):
            s = 0
            for n in range(N):
                if i[n] == 1:
                    s += A[n][m]
            if s >= X:
                c += 1
        if c == M:
            money = 0
            for n in range(N):
                if i[n] == 1:
                    money += A[n][0]
            ans = min(ans, money)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
array = [ list(map(int,input().split())) for _ in range(N) ]
ans = 10**18
for i in range ( 2**N ):
  price = 0
  skill = [0]*M
  count = 0
  for k in range(N):
    if ( i >> k ) & 1:
      price += array[k][0]
      for j in range (M):
        skill[j] += array[k][j+1]
  for t in range(M):
    if skill[t] < X:
      break
    else:
      count += 1
    if count == M:
      ans = min(price,ans)
      
print( -1 if ans == 10**18 else 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 = float("inf")
for i in range(1, n+1):
  for i1 in combinations(ca, i):
    nums = [0]*(m+1)
    for i2 in i1:
      for i3 in range(m+1): nums[i3] += i2[i3]
    if min(nums[1:]) >= x:
      if nums[0] < ans: ans = nums[0]
if ans == float("inf"): print(-1)
else: print(ans)