#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1024;
int n, m, v[N], w[N], f[N]; // f[N] 储存背包容量为 m 的能装的最大价值

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);

    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= v[i]; j -- ) // m 为背包容量
            f[j] = max(f[j], f[j - v[i]] + w[i]); // j - v[i] 为装入当前物品后背包多出的容量
/* 两层循环：
1. 第一层：遍历整个数组
2. 第二层：更新最大价值
*/
    printf("%d", f[m]);
    return 0;
}

// 1. 读入数据

// 2. D P 循环：重复子问题 + 最优化子结构

// 3. 输出结果

DP循环：

这个部分是解决问题的核心。它使用动态规划的方法来计算可以放入背包的物品的最大价值。
for(int i = 1; i <= n; i ++ )：这个循环遍历所有物品。
for(int j = m; j >= v[i]; j -- )：这个内循环从最大容量m开始，递减至物品i的价值v[i]，确保背包至少有空间放下当前物品。
f[j] = max(f[j], f[j - v[i]] + w[i]);：这行是 $DP$ 的核心。它决定了是否将当前物品i加入背包。它比较当前j容量下不加入物品i的最大价值f[j]和加入物品i后的总价值f[j - v[i]] + w[i]，取两者之间的最大值更新f[j]。

$pair$ 写法：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

#define v first
#define w second
using namespace std;
typedef pair<int, int> PII;

const int N = 1024;
PII bp[N];
int n, V, a[N];

int main(){
    scanf("%d%d", &n, &V);
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &bp[i].v, &bp[i].w);

    for(int i = 1; i <= n; i ++ ){
        for(int j = V; j >= bp[i].v; j -- ) a[j] = max(a[j], a[j - bp[i].v] + bp[i].w);
    }

    printf("%d", a[V]);
    return 0;
}