벼락치기

• 전형적인 0-1 knapsack 문제. 무게(=공부시간)의 합이 배낭 용량(=남은 시간)을 초과하지 않으면서 가치(=점수)합을 최대화 시키도록 물건(=과목)들을 선택하면 하면 된다
• 풀이는 평범한 배낭 참고.
• 다만 평범한 배낭과는 n=100, w_i<1000인 것은 똑같지만, W가 100,000과 10,000으로 차이가 있다. W=100,000 이었던 평범한 배낭은 실제로 가능한 무게합들이 스파스해서 dict를 써서 dp table을 만드는 편이 더 효율적이었지만, W=10,000인 이 문제에서는 그냥 list로 dp table을 만드는것이 더 효율적이다.

"""Solution code for "BOJ 14728. 벼락치기".

- Problem link: https://www.acmicpc.net/problem/14728
- Solution link: http://www.teferi.net/ps/problems/boj/14728

Tags: [knapsack] [dp]
"""

import sys


def main():
    N, T = [int(x) for x in sys.stdin.readline().split()]
    K_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    dp = [0] * (T + 1)
    for k, s in K_and_S:
        for t, dp_t, dp_p in zip(range(T + 1), dp, dp[k:]):
            if dp_p + s > dp_t:
                dp[t] = dp_p + s

    print(max(dp))


if __name__ == '__main__':
    main()