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 = [0]*N
A = [[] for _ in range(N)]
for i in range(N):
    CA = list(map(int,input().split()))
    C[i] = CA[0]
    A[i] = CA[1:]

INF = 10**10
ans = INF
for i in range(2**N):
    res = 0
    temp = i
    state = [False]*N
    for j in range(N):
        state[j] = temp&1
        temp >>= 1
        if temp==0:
            break
    
    D = [0]*M
    for j in range(N):
        if not state[j]:
            continue
        res += C[j]
        for t in range(M):
            D[t] += A[j][t]
    
    flag = True
    for d in D:
        if d<X:
            flag = False
            break
    if flag:
        ans = min(ans,res)

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

Submission status: Accepted

Solution code:
from itertools import product

n, m, x = map(int, input().split())
price = [0] * (n)
AA = []
for i in range(n):
    c, *A = map(int, input().split())
    price[i] = c
    AA.append(A)

kumiawase = list(product([0, 1], repeat=n))

ans = 10 ** 20
flag = 0
for kumi in kumiawase:
    temp = 0
    memo = [0] * (m)
    for i in range(n):
        if kumi[i] == 1:
            temp += price[i]
            for j in range(m):
                memo[j] += AA[i][j]
    for j in range(m):
        if memo[j] >= x:
            continue
        else:
            temp = -1
    if temp > 0:
        flag = 1
        ans = min(ans, temp)

if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M,X = inputIL()
B = inputILL(N)

best = 1e20

for i in range(pow(2,N)):
  learn = [0 for _ in range(M)]
  cost = 0
  for j in range(N):
    if i>>j & 1:
      cost += B[j][0]
      for k in range(M):
        learn[k] += B[j][k+1]
  check = 1
  for item in learn:
    if item < X:
      check = 0
  if check:
    best = min(best,cost)
    
if best == 1e20:
  print(-1)
else:
  print(best)

Submission status: Accepted

Solution code:



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):
    cost = 0
    point = [0] * M
    for i in range(N):
        if bit & (1 << i):
            cost += CA[i][0]
            for j in range(M):
                point[j] += CA[i][j+1]
    flag = True
    for i in range(M):
        if point[i] < X:
            flag = False
            break
    if flag:
        ans = min(cost, ans)


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

Submission status: Accepted

Solution code:
from itertools import combinations

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


ans = 10**10

for i in range(2**n):
    b = format(i,'b').zfill(n)
    d = [0]*m
    c =0
    for j in range(n):
        if b[j]=='1':
            for k in range(m):
                d[k]+=a[j][k+1]
            c += a[j][0]
    flag = 1
    for y in d:
        if y<x:
            flag = 0
    if flag:
        ans = min(ans,c)

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

Submission status: Accepted

Solution code:
import sys

inf = float('inf')

n, m, x = map(int, sys.stdin.readline().split())
C = []
A = []
for _ in range(n):
    c, *a = map(int, sys.stdin.readline().split())
    C.append(c)
    A.append(a)

def main():
    ans = inf
    for i in range(1 << n):
        res = [0] * m 
        cost = 0
        for j in range(n):
            if i >> j & 1:
                cost += C[j]
                for k in range(m):
                    res[k] += A[j][k]
        for r in res:
            if r < x: break
        else:
            ans = min(ans, cost)
    if ans == inf:
        print(-1)
    else:
        print(ans)


                
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,m,x=map(int,input().split())
    data=[]
    for i in range(n):
        a=list(map(int,input().split()))
        data.append(a)
    ans=10000000
    for i in range(2**n):
        res=[0]*m
        price=0
        flg=1
        for j in range(n):
            if (i>>j)&1:
                price+=data[j][0]
                for k in range(m):
                    res[k]+=data[j][k+1]
        for j in range(m):
            if res[j]<x:
                flg=0
                break
        if flg==1:
            ans=min(ans,price)
    if ans==10000000:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np
N, M, X = map(int, input().split())
CA = np.array([input().split() for _ in range(N)], dtype=np.int64)
C = CA[:, 0]
A = CA[:, 1:]

inf = 10**18
ans = inf
for p in product(range(2), repeat=N):
    p = np.array(p)
    ok = (p[:, None] * A).sum(axis=0)
    if (ok >= X).all():
        cost = (p * C).sum()
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
book_cost = [0]*n
book_skill = [[0]*m for _ in range(n)]
for i in range(n):
    li = list(map(int,input().split()))
    book_cost[i] = li[0]
    for j in range(m):
        book_skill[i][j] = li[j+1]
max_cost = 10000000
for i in range(2**n):
    cost = 0
    skill = [0]*m
    for j in range(n):
        if i >> j & 1:
            cost += book_cost[j]
            for k in range(m):
                skill[k] += book_skill[j][k]
    for j in range(m):
        if skill[j] < x:
            break
    else:
        max_cost = min(max_cost,cost)
if max_cost == 10000000:
    print(-1)
else:
    print(max_cost)

Submission status: Accepted

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

ans = -1

for i in range(1 << n):
    xi = 0
    algo = [0] * m
    money = 0
    for j in range(n):
        if i & (1 << j):
            money += c[j]
            for k in range(m):
                algo[k] += a[j][k]

    flag = True

    for al in algo:
        if al < x:
            flag = False

    if flag:
        if ans != -1:
           ans = min(ans, money)
        else:
            ans = money


print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
book = []
for _ in range(n):
  book.append(list(map(int,input().split())))
time = [0 for _ in range(n)]
def nex(time):
  for d in range(n):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  cnt = [0 for _ in range(m)]
  ans = 0
  for i in range(n):
    c = book[i][0]
    a = book[i][1:]
    if time[i] == 1:
      for j in range(m):
        cnt[j] += a[j]
      ans += c
  for j in range(m):
    if cnt[j] < x:
      break
  else:
    can.append(ans)
  time = nex(time)
if can:
  print(min(can))
else:
  print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def main():
    N, M, X = map(int, input().split())
    C = [0]*N
    A = [None]*N
    for i in range(N):
        C[i], *A[i] = map(int, input().split())

    min_money = INF
    # 全探索
    for i in range(1 << N):
        tot = [0]*M
        money = 0
        for n in range(N):
            if bit(i, n):
                money += C[n]
                for j in range(M):
                    tot[j] += A[n][j]

        if all(tot[j] >= X for j in range(M)):
            min_money = min(money, min_money)
    if min_money == INF:
        print(-1)
    else:
        print(min_money)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,X = [int(hoge) for hoge in input().split()]
CE = [[int(hoge) for hoge in input().split()] for n in range(N)]
curmin = 100000000000000000
ans = -1
for i in range(2**12):
    A = [0]*M
    cost = 0
    for n,CA in enumerate(CE):
        if (i >> n) & 1:
            cost += CA[0]
            for m in range(M):
                A[m] += CA[m+1]
    if all([x >= X for x in A]):
        curmin = min(curmin,cost)
        ans = curmin
print(ans)

Submission status: Accepted

Solution code:
#code
N,M,X=map(int,input().split())
book=[]
for i in range(N):
    temp=list(map(int,input().split()))
    book.append(temp)
ans=10**9    
for i in range(2**N):
    temp=bin(i)[2:]
    temp='0'*(N-len(temp))+temp
    cost=0
    ls=[0 for j in range(M)]
    for j in range(N):
        if(temp[j]=='1'):
            cost+=book[j][0]
            for k in range(1,M+1):
                ls[k-1]+=book[j][k]
    flag=True
    for j in range(M):
        if(ls[j]<X):
            flag=False
    if(flag):ans=min(ans,cost)
if(ans==10**9):print(-1)
else:print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m,x=map(int,input().split())
A=[]
for i in range(n):
    c=list(map(int,input().split()))
    A.append(c)
C=10**10
for i in range(2**n):
    al=[0]*m
    cost=0
    for j in range(n):
        if (i>>j)%2==1:
            cost+=A[j][0]
            for k in range(m):
                al[k]+=A[j][k+1]
    if min(al)>=x:
        if C>cost:
            C=cost
if C==10**10:
    print(-1)
else:
    print(C)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(N)]
ans = float('inf')
for i in range(2**N):
    tca = [0]*(M+1)
    for j in range(N):
        if i & (1 << j) > 0:
            for k in range(M+1):
                tca[k] += ca[j][k]
    if min(tca[1:]) >= X:
        ans = min(ans, tca[0])

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

Submission status: Accepted

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

ans = sum(c) + 1
for i in range(2**n):
    tmp = 0
    com = [0] * m
    for j in range(n):
        if i >> j & 1:
            tmp += c[j]
            for k in range(m):
                com[k] += a[j][k]
    ok = True
    for k in range(m):
        if com[k] < x:
            ok = False
            break
    if ok:
        ans = min(ans, tmp)
if ans == sum(c) + 1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
ans = float("inf")

for i in range(2**N):
    now = bin(i)[2:].zfill(N)  # now[i]: 参考書iを買う
    res = 0
    An = [0] * M
    for n in range(N):
        if now[n] == "1":
            res += A[n][0]
            An = [An[j] + A[n][j+1] for j in range(M)]
    if min(An) >= X:
        ans = min(ans, res)

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,x = na()
c = []

for i in range(n):
    cc = na()
    c.append(cc)

ans = 1000000000000

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

if ans == 1000000000000:
    print(-1)
    exit()

print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = []
a = []
ans = 10**9
for i in range(n):
    p = list(map(int,input().split()))
    c.append(p[0])
    a.append(p[1:])
for i in range(2**n):
    point = [0]*m
    res = 0
    for j in range(n):
        
        if (i>>j)%2:
            res += c[j]
            for k in range(m):
                point[k] += a[j][k]
    point.sort()
    if point[0] >= x:
        ans = min(ans,res)
    
if ans == 10**9:ans = -1
            
print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
L = list()
INF = float('INF')
ans = INF
for i in range(N):
  L.append(list(map(int, input().split())))
for i in range(1<<N):
  a = [0]*M
  flag = 1
  check = list()
  cost = 0
  for j in range(N):
    if i&(1<<j):
      check.append(j)
  for j in check:
    cost += L[j][0]
    for m in range(M):
      a[m] += L[j][m+1]
  for i in range(M):
    if(a[i] < X):
      flag = 0
  if(flag == 1):
    ans = min(ans, cost)
if(ans == INF):
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

n, m, x = [int(x) for x in input().split()]
c = []
a = []
for _ in range(n):
    c_, *a_ = [int(x) for x in input().split()]
    c.append(c_)
    a.append(a_)
ans = float("inf")
for i in range(2**n):
    i_bin = bin(i)[2:].zfill(n)
    ans_ = 0
    a_ = [0]*m
    for j in range(n):
        if i_bin[j] == "1":
            ans_ += c[j]
            for k in range(m):
                a_[k] += a[j][k]
    flag = 1
    for k in range(m):
        if a_[k] < x:
            flag = 0
            break
    if flag:
        ans = min(ans, ans_)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

bit = 2 << 12

ANS = 10 ** 10
ok = False
for i in range(bit):
    USE = [False] * N

    for j in range(N):
        USE[j] = i & 1
        i >>= 1

    m = 0
    POINTS = [0] * M
    for j in range(N):
        if not USE[j]:
            continue

        m += CAS[j][0]

        for k in range(M):
            POINTS[k] += CAS[j][k + 1]

    P = [X <= p for p in POINTS]

    if all(P):
        ok = True
        ANS = min(ANS, m)


if not ok:
    print("-1")
else:
    print(ANS)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,m,x = map(int,readline().split())
lst1 = []
for i in range(n):
    lst1.append(list(map(int,readline().split())))
ans = 10**12
for i in range(1<<n):
    res = [0]*m
    cost = 0
    for j in range(n):
        if i>>j&1:
            cost += lst1[j][0]
            for idx,k in enumerate(lst1[j][1:]):
                res[idx] += k


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

print(ans if ans != 10**12 else -1)

Submission status: Accepted

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

ans = 10**7
for i in range(2**n):
    uns = [0 for _ in range(m)]
    tmp_ans = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            for k in range(1,m+1):
                uns[k-1] += book_list[j][k]  # フラグが立っていたら bag に果物を詰める
            tmp_ans += book_list[j][0]  # 買い物累計額にも加算
        if min(uns) >= x:
            ans = min(ans, tmp_ans)
if ans == 10**7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

B = [list(map(int,input().split())) for i in range(N)]
ans = 10**28
for i in range(2**N):
    cost = 0
    alg = [0]*M
    for j in range(N):
        if i & 2**j>0:
            cost += B[j][0]
            for k in range(M):
                alg[k] += B[j][1+k]
    flag = True
    for k in range(M):
        if alg[k]<X:
            flag=False
            break
    if flag:
        ans = min(cost,ans)

if ans <10**28:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
INF = float('inf')

N, M, X = map(int, input().split())
Cs = []
Ass = []
for _ in range(N):
    C, *As = map(int, input().split())
    Cs.append(C)
    Ass.append(As)
#print('Ass:')
#for As in Ass:
#    print(As)

ans = INF
for S in range(1<<N):
    Bs = [0] * M
    cost = 0
    for i in range(N):
        if (S>>i)&1:
            cost += Cs[i]
            for j in range(M):
                Bs[j] += Ass[i][j]
        if min(Bs) >= X:
            ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
l = []
for i in range(n):
    l1 = list(map(int,input().split()))
    l.append(l1)
ansl = []
for i in range(2**n):
    now = 0
    nl = [0 for i in range(m)]
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(1,m+1):
                nl[k-1] += l[j][k]
            now += l[j][0]
    key = 0
    #print(nl)
    for j in range(m):
        if nl[j] < x:
            key = 1
    if key == 0:
        ansl.append(now)
if len(ansl) > 0:
    print(min(ansl))
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
d=[]
for i in range(n):
    s=list(map(int,input().split()))
    d.append(s)
ans=float("inf")
for i in range(2**n):
    string=format(i,"0%ib"%(n))
    c=0
    data=[0 for _ in range(m+1)]
    for k in range(n):
        if string[k]=="1":
            for j in range(1,m+1):
                data[j]+=d[k][j]
            c+=d[k][0]
    if all(data[j]>=x for j in range(1,m+1)):
        ans=min(ans,c)
if ans!=float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n,m,x = myinput()
CA = mylistinput(n)

ans = INF
for i in range(2**n):
    cost = 0
    ls = [0]*m
    for j in range(n):
        if i & (2**j):
            c = CA[j][0]
            a = CA[j][1:]
            cost += c
            for k in range(m):
                ls[k] += a[k]
    if min(ls)>=x:
        ans = min( ans, cost )

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

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    ans = 10 ** 9 + 7
    for i in range(2 ** N):
        x = [0 for _ in range(M)]
        money = 0
        for j in range(N):
            if ((i >> j) & 1):
                money += C[j]
                for k, a in enumerate(A[j]):
                    x[k] += a
        flag = True
        for r in x:
            if r < X:
                flag = False
                break
        if flag:
            ans = min(ans, money)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
d=[]
for i in range(n):
    a.append(list(map(int,input().split())))
for i in range(2**n):
    b='0'*(n-len(bin(i))+2)+bin(i)[2:]
    s=[0]*m
    c=0
    f=1
    for j in range(n):
        if b[j]=='1':
            for k in range(m):
                s[k]+=a[j][k+1]
            c+=a[j][0]
    for j in range(m):
        if s[j]<x:
            f=0
    if f==1:
        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())
ca = []

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

ans = 1e10


for i in range(2**N):
    flag = True
    sanko = [0]*M
    cost = 0
    for j in range(N):
        tmp = 0
        if (i>>j)&1:
            cost += ca[j][0]
            for h in range(1,M+1):
                sanko[h-1] += ca[j][h]
    for s in sanko:
        if s < X:
            flag = False
            break
    if flag:
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
from itertools import product
def main():
    n, m, x = map(int, input().split())
    bk = [list(map(int, input().split())) for _ in range(n)]
    f = False
    ans = float("inf")
    for arr in product([True, False], repeat=n):
        mon = 0
        t = [0]*m
        for i in range(n):
            if arr[i]:
                mon += bk[i][0]
                for j in range(1, m+1):
                    t[j-1] += bk[i][j]
        sf = True
        for i in range(m):
            if t[i] < x:
                sf = False
                break
        if sf:
            f = True
            if mon < ans:
                ans = mon
    if f:
        print(ans)
    else:
        print("-1")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
b=[]
for i in range(2**n):
  b.append(format(i,'0'+str(n)+'b'))
ans=[]
for i in range(2**n):
  y=0
  ct=[0]*m
  for j in range(n):
    if b[i][j]=='1':
      y+=l[j][0]
      for k in range(1,m+1):
        ct[k-1]+=l[j][k]
  ct2=0
  for j in range(m):
    if ct[j]>=x:
      ct2+=1
  if ct2==m:
    ans.append(y)
if len(ans)==0:
  print(-1)
else:
  print(min(ans))