백준(BOJ) 14728 벼락치기 **

#DP #Knapsack 알고리즘

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 10005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
int n, m, a, b, dp[10001];
int main()
{
    scanf("%d %d", &n, &m);
    while (n--)
    {
        scanf("%d %d", &a, &b);
        for (int i = m; i >= a; i--)
            dp[i] = max(dp[i], b+dp[i - a]);
    }
    printf("%d", dp[m]);
    return 0;
}