AtCoder Beginner Contest 167 [ C - Skill Up ] https://atcoder.jp/contests/abc167/tasks/abc167_c

abc167_c.py

'''
[問題]
https://atcoder.jp/contests/abc167/tasks/abc167_c

[解法]
N <= 12 と小さいことからbit全探索が想定解だったが、Pythonのitertoolsを使った組み合わせ生成でも充分早かった

[結果]
Python(3.8.2) AC 89ms
PyPy3(7.3.0) AC 79ms
'''

import sys
import itertools

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

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

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

# 総当たりで全組み合わせを調べる
ans = INF

for i in range(1,N+1):
    # combinationsで、参考書のリストからi個選んだ時の組み合わせを生成する
    kumi_list = list(itertools.combinations(list(range(N)), i))

    for k in kumi_list:
        price = 0
        s = [0] * M
        for j in range(i):
            index = k[j]
            # 参考書の金額合計
            price += C[index][0]
            # スキルアップの合計計算
            for t in range(M):
                s[t] += C[index][t+1]

        out = False
        for ss in s:
            # スキルアップが目標を達成しているか？
            if ss < X:
                out = True
                break

        # スキルアップが目標を達成しているなら、ansと比較
        if out == False:
            ans = min(ans, price)

if ans == INF:
    # ansの値が更新されてないなら、成立しない
    print(-1)
else:
    print(ans)