1번

01.py

import copy
import sys


def solve():
    N, K, M = list(map(int, sys.stdin.readline().split()))
    all_mvs = [[0, 0]]
    loaded = []
    answer = 0

    for _ in range(N):
        m, v = list(map(int, sys.stdin.readline().split()))
        all_mvs.append([m, v])

    for _ in range(K):
        local_mvs = []

        for idx in range(len(all_mvs)):
            if idx not in loaded:
                local_mvs.append(all_mvs[idx])

        dp = [[0 for _ in range(M + 1)] for _ in range(len(local_mvs))]
        dp2 = [[[] for _ in range(M + 1)] for _ in range(len(local_mvs))]

        for row in range(1, len(local_mvs)):
            for col in range(1, M + 1):

                m, v = local_mvs[row]
                if col < m:
                    dp[row][col] = dp[row - 1][col]
                    dp2[row][col] = copy.deepcopy(dp2[row - 1][col])
                else:
                    if dp[row - 1][col] < dp[row - 1][col - m] + v:
                        dp[row][col] = dp[row - 1][col - m] + v
                        dp2[row][col] = copy.deepcopy(dp2[row - 1][col - m])
                        dp2[row][col].append(row)
                    else:
                        dp[row][col] = dp[row - 1][col]
                        dp2[row][col] = copy.deepcopy(dp2[row - 1][col])

        answer += dp[len(local_mvs) - 1][M]
        loaded += dp2[len(local_mvs) - 1][M]

    print(answer)


# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    solve()