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 = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]
kouho = []
for i in range(2**N):
  skill = [0]*M
  price = 0
  for j in range(N):
    if ((i>>j) & 1):
      skill = [x+y for (x, y) in zip(skill, A[j][1:])]
      price += A[j][0]
  flag = 1
  for k in skill:
    if k < X:
      flag = 0
  if flag:
    kouho.append(price)
if len(kouho):
  print(min(kouho))
else:
  print(-1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = [0]*n
a = []
ans = float('inf')

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

for bit in range(1<<n):
    s = [0]*m
    sumnum = 0
    for i in range(n):
        if 1 & (bit>>i):
            sumnum += c[i]
            for j in range(m):
                s[j] += a[i][j]
    flag = True
    for k in range(m):
        if s[k] < x:
            flag = False
            break
    if flag:
        ans = min(ans, sumnum)

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

Submission status: Accepted

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

n,m,x = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(n)]
ans = float('inf')
for num in range(1,n+1):
    for e in combinations(range(n),num):
        cost = 0
        under = [0 for _ in range(m)]
        for f in e:
            cost += c[f][0]
            for i in range(m):
                under[i] += c[f][i+1]
        if min(under) >= x:
            ans = min(ans,cost)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

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

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

        ci = bi[0]
        c.append(ci)

        ai = bi[1:]
        a.append(ai)

    ans = float('inf')

    # KeyInsight: bit演算を使った全探索
    # 全パターン(選ぶ/選ばないを1/0で表現)を列挙
    for i in range(1 << n):
        cost = 0
        tmp = [0 for _ in range(m)]

        for j in range(n):
            # あるビットが立っているかどうか(1かどうか)を判定
            if (i >> j & 1):
                cost += c[j]

                for index, aii in enumerate(a[j]):
                    tmp[index] += aii

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n,m,x = map(int,input().split())
    c = [list(map(int,input().split())) for _ in range(n)]
    ans = float('inf')
    for num in range(1,n+1):
        for e in combinations(range(n),num):
            cost = 0
            under = [0 for _ in range(m)]
            for f in e:
                cost += c[f][0]
                for i in range(m):
                    under[i] += c[f][i+1]
            if min(under) >= x:
                ans = min(ans,cost)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)
 
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product

import numpy as np

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    n, m , x = map(int, input().split())
    c_list = []
    a_list = []
    for _ in range(n):
        c, *a = list(map(int, input().split()))
        a_list.append(a)
        c_list.append(c)
    # print(a_list)
    ans = float("inf")
    for pattern in product((0,1), repeat=n):
        arr = np.array([a_list[i] for i in range(n) if pattern[i] == 1])
        if arr.sum(axis=0).min() >= x:
            cost = sum([c_list[i] for i in range(n) if pattern[i] == 1])
            ans = min(ans, cost)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import itertools
import numpy as np


def main():

    n, m, x= map(int, input().split())
    matrix = np.array([list(map(int, input().split())) for _ in range(n)], dtype=np.int32)

    out = 10**18
    for i in itertools.product([False,True], repeat=n):
        row_sum = np.sum(matrix[np.where(i)], axis=0)
        if m == np.count_nonzero(row_sum[1:] >= x):
            out = min(out, row_sum[0])

    if out == 10**18:
        print('-1')
    else:
        print(out)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, x = [int(x) for x in input().split()]
c = []
a = []
count = 0

for i in range(n):
    tmp = [int(x) for x in input().split()]
    c.append(tmp.pop(0))
    a.append(tmp)

min = sum(c)+1

for i in range(1<<n):
    cost = 0
    skill = [0]*m
    for j in range(n):
        s = []
        if(i>>j&1):
            cost += c[j]
            for k in range(m):
                skill[k] += a[j][k]
    for s in skill:
        if(s < x):
            break
    else:
        if(cost < min):
            min = cost

if(min == sum(c)+1):
    print('-1')
else:
    print(min)

Submission status: Accepted

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



ans=10000000000000
for j in range(1,2**(N+1)-1):
    combinationlist=list(map(int, [i for i in format(2**(N+1)+j,'b')]))
    del combinationlist[0]
    sumoflist=[sum(combinationlist[s]*List[s][k] for s in range(N)) for k in range(M+1)]
    flag=True
    for t in range(1,M+1):
        if sumoflist[t]<X:
            flag=False
            break
    if flag and sumoflist[0]<ans:
        ans=sumoflist[0]

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

Submission status: Accepted

Solution code:
#167
#c
import sys
import itertools
import numpy
n,m,x  = map(int, input().split())
zentan = itertools.product([0,1],repeat = n)
condi  = []
for i in range(n):
    ln = list(map(int, input().split()))
    condi.append(ln)
min_cost = 10**10
for i in zentan:# e.g.   i = (0,0, ...) len(i ) = n
    cost = 0
    skills= [0]*m
    # cost 
    for n1, n2 in enumerate(i):# n1 = 0~n-1, n2 = i[n1]
        cost += condi[n1][0]*n2
        #skills
        for n3 in range(m): # n3 = 0~m-1
            skills[n3] += condi[n1][n3+1]*n2
    if min(skills) >= x and cost < min_cost:
        min_cost = cost
    
        

            
            
if min_cost<10**10:
    print(min_cost)
else:
    print('-1')

Submission status: Accepted

Solution code:
#167C bit探索
def main():
    import sys, itertools
    import numpy as np
    N,M,X = map(int, sys.stdin.readline().split())
    L = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #print(L)
    ans =-1
    for i in range(2**N):
        result = np.array([0 for _ in range(M+1)])
        for j in range(N): # (i >> j) & 1  2進数のj桁目と1の論理積
            if (i >> j) & 1==1:
                result += np.array(L[j])
        if np.all(result[1:] >=X):
            #print(result)
            if ans ==-1 or result[0] < ans:
                ans = result[0]
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
INF = 10 ** 18  # 定数は大文字　INF＝Infinity（無限大）
ans = INF
li = []
for i in range(n):
    li.append(list(map(int, input().split())))


for i in range(2 ** n):
    cost = 0
    know = [0]*m  # アルゴリズムM個
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            # フラグが立っていたら
            cost += li[j][0]
            for k in range(m):
                know[k] += li[j][k + 1]

    knowbool = True
    for i in range(m):  # 理解度がXを超えているか
        if (know[i] < x):
            knowbool = False

    if (knowbool):
        ans = min(ans, cost)


if (ans == INF):  # ansが更新されていない　つまりどのパターンをとっても理解度Xを超えなかったら
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from itertools import product
    import sys
    input = sys.stdin.readline

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

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

        ci = bi[0]
        c.append(ci)

        ai = bi[1:]
        a.append(ai)

    ans = float('inf')

    for p in list(product(range(2), repeat=n)):
        tmp = [0 for _ in range(m)]
        cost = 0

        for index, pi in enumerate(p):
            if pi == 1:
                for idx, aii in enumerate(a[index]):
                    tmp[idx] += aii

                cost += c[index]

        is_ok = True

        for t in tmp:
            if t < x:
                is_ok = False
                break

        if is_ok:
            ans = min(ans, cost)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

INF = 10 ** 9
ans = INF
c = [0] * n
a = [[] for _ in range(n)]
for i in range(n):
    books = list(map(int, input().split()))
    c[i] = books[0]
    a[i] = books[1:]

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

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

Submission status: Accepted

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

ans = None
for bit in range(1 << N):
    atotals = [0] * M
    ctotal = 0
    for i in range(N):
        if bit & (1 << i):
            ca = CA[i]
            for j, a in enumerate(ca[1:]):
                atotals[j] += a
            ctotal += ca[0]

    if all(map(lambda atotal: atotal >= X, atotals)):
        if ans is None:
            ans = ctotal
        else:
            ans = min(ans, ctotal)
if ans is None:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ans=100000000000

for i in range(1, 2**N):
  price=0
  rikaido = [0]*M
  for j in range(N):
    if i>>j & 1:
      price += int(CAAA[j][0])
      for k in range(M):
        rikaido[k] += int(CAAA[j][k+1])
  for l in rikaido:
    if l < X:
      break
  else:
    ans = min(ans, price)
if ans == 100000000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,m,x=map(int,input().split())
A=[]
ALL=[]
ans=10**7
for i in range(n):
    A.append(list(map(int,input().split())))
for i in range(2**n):
    S=[0 for _ in range(m+1)]
    buy=[]
    for j in range(n):
        if ((i>>j) & 1):
            buy.append(A[j])
        #for k in range(m+1):
    for j in range(m+1):
        for k in range(len(buy)):
            S[j]+=buy[k][j]
    #print(S)
    flag=0
    for j in range(1,m+1):
        if S[j]<x:
            flag=1
    if flag==0:
        ans=min(ans,S[0])
if ans==10**7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

from itertools import product
import numpy as np

INF = 1001001001
ans = INF

for i in product(range(2), repeat=n): # product(range(2),n)でn桁のbit全探索が可能
    tmp_price = 0
    tmp_und = np.zeros((m, ))
    for j in range(n):
        if i[j]:
            c, *a = ca[j]
            # Pythonでは、タプルやリストの要素を展開して複数の変数に代入できる。アンパック代入などと呼ばれる
            # 変数の数が要素の数よりも少ない場合、変数名にアスタリスク*をつけると、要素がリストとしてまとめて代入される
            tmp_price += c
            tmp_und += np.array(a, dtype=np.int64)
    tmp_und = tmp_und.tolist()
    if all(tmp_und_ele >= x for tmp_und_ele in tmp_und):
        ans = min(ans, tmp_price)

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

Submission status: Accepted

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

ans=100000000000

for i in range(1, 2**N):
  price=0
  rikaido = [0]*M
  for j in range(N):
    if i>>j & 1:
      price += int(CAAA[j][0])
      for k in range(M):
        rikaido[k] += int(CAAA[j][k+1])
        for l in rikaido:
          if l < X:
            break
        else:
          ans = min(ans, price)
if ans == 100000000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import numpy as np
    from itertools import product

    n, m, x = list(map(int, readline().split()))
    a, c = [], []
    for i in range(n):
        c_temp, *a_temp = list(map(int, readline().split()))
        c.append(c_temp)
        a.append(a_temp)

    a = np.array(a)
    ans = INF

    for bit in product(range(2), repeat=n):
        price_total = 0
        learn_total = np.array([0] * m)
        for i in range(n):
            if bit[i] == 1:
                price_total += c[i]
                learn_total += a[i]
        if np.all(learn_total >= x):
            ans = min(ans, price_total)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 1000000000
for k in range(1, 2**N):
  price = 0
  rikaido=[0]*M
  for l in range(N):
    if k>>l & 1:
      #if CAAA[m][1] < price:
      price += int(CAAA[l][0])
      for t in range(M):
        rikaido[t] += int(CAAA[l][t+1])
        for r in rikaido:
          if r < X:
            break
        else:
          ans = min(ans, price)
if ans == 1000000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:





if __name__ == "__main__":
    n, m, x = map(int, input().split())

    c = []
    a = []

    for _ in range(n):
        cost, *rikaido = map(int, input().split())
        c.append(cost)
        a.append(rikaido)

    INF = float("inf")
    ans = INF
    
    for bit in range(1 << n):
        price_total = 0
        learn_total = [0] * m

        for i in range(n):
            if (bit >> i) & 1:
                # 買う場合
                price_total += c[i]
                for j in range(m):
                    learn_total[j] += a[i][j] 
        
        # 判定
        judge = True
        for j in range(m):
            if learn_total[j] < x:
                judge = False
                break
        
        if judge:
            ans = min(ans, price_total)
        
    if ans == INF:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

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

def dfs(asum, b):
    global n, m, x
    rst = 10 ** 8
    if b == n:
        if all(asum[i] >= x for i in range(1, m + 1)):
            rst = asum[0]
    else:
        rst = min(rst, dfs(asum, b+1))
        asum2 = tuple(asum[i] + c[b][i] for i in range(m + 1))
        rst = min(rst, dfs(asum2, b+1))

    return rst

rst = dfs(tuple([0] * (m + 1)), 0)
ans = rst if rst < 10 ** 8 else -1
print(ans)

Submission status: Accepted

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

ans = 10**10
for i in range(2**n):
    und = [0 for i in range(m)]
    f = "{:b}".format(i)
    s = f.zfill(n)
    mm = 0
    for j in range(len(s)):
        if s[j] == '1':
            for k in range(m):
                und[k] += know[j][k]
            mm += prace[j]
    for j in range(m):
        if und[j] < x:
            break
    else:
        ans = min(ans, mm)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-05-10 20:11
# @url:https://atcoder.jp/contests/abc167/tasks/abc167_c
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    nmx=list(map(int,input().split()))
    n,m,x=nmx[0],nmx[1],nmx[2]
    nums=[]
    c=[]
    for i in range(n):
        temp=list(map(int,input().split()))
        c.append(temp[0])
        nums.append(temp[1:])
    # print (c)
    # print (nums)
    combin=[]
    for i in range (1,n+1):
        combin.extend(list(itertools.combinations(range(n),i)))
    mn=[]
    for b in combin:
        temp,cost=[0]*m,0
        for y in b:
            for i in range(len(nums[y])):
                temp[i]+=nums[y][i]
            cost+=c[y]
        # print (temp,cost)
        flag=True
        for j in range(m):
            if temp[j]<x:
                flag=False
                break
        if flag:
            mn.append(cost)
    # print (mn)
    print (min(mn) if len(mn)>0 else -1)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools


def m():
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split())) for _ in range(N)]
    ans = float('inf')
    for i in itertools.product([True, False], repeat=N):
        tmp = [0] * (M + 1)
        for j, v in enumerate(i):
            if v:
                for k in range(M + 1):
                    tmp[k] += CA[j][k]
        f = 1
        for p in range(1, M + 1):
            if tmp[p] < X: f = 0
        if f: ans = min(ans, tmp[0])
    return ans if ans != float('inf') else "-1"


print(m())

Submission status: Accepted

Solution code:
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)

min_prices = 10**9
for i in range(1 << N):#パターン数
    prices = 0
    rikaido = [0] * M
    for j in range(N): #000 ~ 111 参考書の組み合わせ
        if ((i >> j) & 1) == 1: #参考書の番号（N冊）#011など
            prices += c[j]
            for k in range(M):#アルゴリズムの理解度加算
                rikaido[k] += a[j][k]
        if all(l>=X for l in rikaido):
            min_prices = min(min_prices,prices)
print(min_prices if min_prices != 10**9 else -1)

Submission status: Accepted

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

minimum = float("inf")
for i in range(2**n):
    select = [0] * n
    a = [0] * m
    money = 0
    for j in range(n):
        if (i>>j)&1:
            select[n-1-j] = 1
    for i, v in enumerate(select):
        if v == 1:
            money += CA[i][0]
            for j, u in enumerate(CA[i][1:]):
                a[j] += u
    if not len([l for l in a if l < x]):
        minimum = min(minimum, money)
print(-1 if minimum == float("inf") else minimum)

Submission status: Accepted

Solution code:
import numpy as np
N, M, X = map(int, input().split())
C = []
A = np.zeros((N, M), dtype=int)
for i in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A[i] = a

S = np.sum(A, axis=0)
if True in (S < X):
    print(-1)
    exit(0)

C_ = []
for i in range(2**N):
    total = 0
    arr = np.zeros((M,),dtype=int)
    for j in range(N):
        if ((i>>j) & 1) == 1:
            total += C[j]
            arr += A[j]
    if True in (arr < X):
        continue
    C_.append(total)
print(min(C_))

Submission status: Accepted

Solution code:
#Solver:Rute
n,m,x = map(int,input().split())
money = []
#データ入力
ls = []
costmin = 10**18
for i in range(n):
  ls.append(list(map(int,input().split())))
#bit全探索
for i in range(2**n+1):
  cost = 0
  #print(now)
  #理解度のリスト
  f = "{{:0{}b}}".format(n)
  now = f.format(i)
  understand = [0]*m
  for j in range(len(now)):
    if now[j] == "1":
      cost += ls[j][0]
      for k in range(m):
        understand[k] += ls[j][k+1]
  #print(understand)
  if min(understand) >= x:
    money.append(cost)
if len(money) == 0:
  print(-1)
else:
  money.sort()
  print(money[0])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys

def main():
    N, M, X = map(int, input().split())
    S = [list(map(int,input().split())) for i in range(N)]
    ret = 10**7
    for i in range(2 ** N):
        TA = [0] * M
        TC = 0
        for j in range(N):    #
            if (i >> j) & 1:  #
                TC += S[j][0]
                for m in range(M):
                    TA[m]+=S[j][m+1]  #
        if min(TA)>=X:
            ret = min(ret, TC)
    if ret == 10**7:
        print(-1)
    else:
        print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

for _ in range(n):
    c, *mi = map(int, input().split())
    C.append(c)
    M.append(mi)

sta = list(product((0, 1), repeat=n))
res = 10**10

for k in sta:
    tmp = 0
    cnt = [0] * m
    for j in range(n):
        if k[j] == 1:
            tmp += C[j]
            for l in range(m):
                cnt[l] += M[j][l]
    if min(cnt) >= x:
        res = min(res, tmp)

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

Submission status: Accepted

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

C=10**7
for i in range(2**N):
  P,T=[0]*M,0
  for j in range(N):
    if i&2**j:
      T+=A[j][0]
      for k in range(M):
        P[k]+=A[j][k+1]
  for j in range(M):
    if P[j]<X:
      break
  else:
    C=min(C,T)

print(-1 if C==10**7 else C)

Submission status: Accepted

Solution code:
import itertools

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

ans=float('inf')

def j(q):
    tmp=0
    cnt=[0]*m
    for i in range(n):
        if q[i]==1:
            tmp+=c[i]
            for j in range(m):
                cnt[j]+=a[i][j]
    if min(cnt)>=x:
        return tmp
    return 0

for tk in itertools.product([0,1],repeat=n):
    h=list(tk)
    ff=j(h)
    if ff!=0:
        ans=min(ans,ff)
if ans==float('inf'):
    print(-1)
    exit()
print(ans)

Submission status: Accepted

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

minimum = float("inf")
for i in range(2**n):
    select = [0] * n
    a = [0] * m
    money = 0
    for j in range(n):
        if (i>>j)&1:
            select[n-1-j] = 1
    for i, v in enumerate(select):
        if v == 1:
            money += CA[i][0]
            for j, u in enumerate(CA[i][1:]):
                a[j] += u
    if all(l >= x for l in a):
        minimum = min(minimum, money)
print(-1 if minimum == float("inf") else minimum)

Submission status: Accepted

Solution code:
n, m, x = map(int,input().split(' '))
a = [[] for i in range(n)]
p = 0
for i in range(n):
    a[i] = list(map(int, input().split(' ')))
sc = 12 * 100001
for i in range(1, 2 ** n):
    bi = '0' * n + bin(i)[2:]
    bi = bi[len(bi) - n:]
    cc = 0
    e = [0] * m
    for j in range(n):
        if bi[j] == '1':
            for k in range(m):
                e[k] += a[j][k + 1]
            cc += a[j][0]
    su =True
    for j in range(m):
        su &= e[j] >= x
    if su:
        sc = min(sc, cc)
sc = -1 if sc > 12 * 100000 else sc
print(sc)

Submission status: Accepted

Solution code:
def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]
[n,m,x] = getlsi()
ls = []
cs = []
for i in range(n):
    tmp = getlsi()
    cs.append(tmp[0])
    ls.append(tmp[1:])
xs = [x] * m
for i in range(n):
    for j in range(m):
        xs[j] -= ls[i][j]
if len([k for k in xs if k > 0]) > 0:
    print(-1)
else:
    cost = 10 ** 5 * 13
    for i in range(1,2 ** n):
        tmp_cost = 0
        tmp_ls = [0] * m
        tmp = "{:0"+str(n)+"b}"
        tmp = tmp.format(i)
        for j in range(n):
            if tmp[j] == "1":
                for k in range(m):
                    tmp_ls[k] += ls[j][k]
                tmp_cost += cs[j]

        if min(tmp_ls) >= x and tmp_cost < cost:
            cost = tmp_cost
    print(cost)

Submission status: Accepted

Solution code:
import math
import copy
from queue import Queue
import heapq
import numpy as np

MOD = 1000000007

#n = int(input())
#b = int(input())
n, m, x = [int(i) for i in input().split()]
table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#s = [int(i) for i in input().split()]
#s = [int(i) for i in range(n)]
#s = [int(input()) for i in range(n)]
#s = input()
#list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]
#dp = [[[0 for _ in range(11)] for _ in range(2)] for _ in range(11)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

min = 1200001
for i in range (2 ** n):
    flag = 1
    for k in range(1,m+1):
        temp = 0
        cost = 0
        for l in range(0,n):
            mask = 1 << l
            if (i & mask):
                temp += table[l][k]
                cost += table[l][0]
        if (temp < x) :
            flag = 0
    if(flag == 1 and min > cost):
        min = cost


if (min == 1200001):
    print("-1")
else:
    print(min)

Submission status: Accepted

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

ans = 10**9
for i in range(2**n):
	cnt = 0
	b = [0 for i in range(m)]
	for j in range(n):
		if (i >> j) & 1:
			cnt += c[j]
			for k in range(m):
				b[k] += a[j][k]
	mn = min(b)
	if mn >= x:
		ans = min(ans,cnt)
if ans == 10**9:
	print (-1)
else:
	print (ans)

Submission status: Accepted

Solution code:
N,M,X = map(int, input().split())
CA_array = list()
for i in range(N):
    CA_list = [int(e) for e in input().split()]
    CA_array.append(CA_list)
    
ans = 13*(10**5)
    
#N<=12なので全探索しても4096.全探索する。
for i in range(2**(N)): #4096
    bit_array = str(bin(i)[2:]).zfill((N))
    #print(bit_array)

    CA_on_bit_array = [0 for _ in range(M+1)]
    
    for j in range(len(bit_array)): #12

        if bit_array[j]=="0":
            #OFF時の処理
            pass
        elif bit_array[j]=="1":
            #ON時の処理
            for k in range(M+1): #13
                CA_on_bit_array[k] += CA_array[j][k]

    #ON・OFFの状態設定後の処理
    for k in range(1,M+1):
        if CA_on_bit_array[k] < X:
            break
    else:
        if CA_on_bit_array[0] < ans:
            ans = CA_on_bit_array[0]

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

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int, input().split())
l = []
for i in range(n):
    l += [list(map(int, input().split()))]

a = 1 <<(n )
r = []
for i in range(a):
    li = np.array([0 for _ in range(m +1)])
    for j in range(n):
        if i & (1 << j):
            li += l[j]
#     print(li)
    for k in range(1,m +1):
        if li[k] < x:
            break
        if k == m:
            r +=[li[0]]
        
if len(r) == 0:
    print('-1')
else:
    print(min(r))

Submission status: Accepted

Solution code:
n, m, x = list(map(int, input().split()))
listA = [list(map(int, input().split())) for i in range(n)]
ans = -1
# n冊 mアルゴリズム x理解度

for i in range(2**n):  # 購入組み合わせ数
    price = 0
    point = [0]*m
    for j in range(n):
        if(i >> j) & 1 == 1: #bit全探索
            price += listA[j][0]
            for k in range(m):
                point[k] += listA[j][k+1]
    if min(point) >= x:
        ans = min(ans, price) if ans != -1 else price

print(ans)