因为比较懒，所以先写个最难题的题解。其他的有空再说吧（可以私信催 ddl 或者听我口胡做法）

J 题题意：完全背包，但是每个物品每次被选后，价值都会产生缩水。

换言之，一个 的 J 题背包，可以等价为这样的 01 背包：

把这个东西用优先队列实现一下，然后跑一遍 01 背包就做完了。

#include <queue>
#include <cstdio>
#define int long long
int init() {
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c & 15);
	return x * f;
}
void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x / 10) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 3e3 + 5;
int dp[N];
int mx(int x, int y) {
	return x > y ? x : y;
}
int w[N * 12], c[N * 12];
std::priority_queue <int> val[N];
signed main() {
	int n = init(), m = init();
	for (int i = 1; i <= n; ++i) {
		int a = init(), b = init();
		val[a].push(b);
	}
	int num = 0;
	for (int j = 1; j <= m; ++j) {
		if (val[j].empty()) continue;
		for (int k = 1; j * k <= m; ++k) {
			int now = val[j].top(); val[j].pop();
			if (now <= 0) break;
			w[++num] = j, c[num] = now;
			val[j].push(now-1);
		}
	}
	for (int i = 1; i <= num; ++i)
		for (int j = m; j >= w[i]; --j)
			dp[j] = mx(dp[j], dp[j - w[i]] + c[i]);
	int ans = 0;
	for (int j = 0; j <= m; ++j)
		ans = mx(ans, dp[j]);
	print(ans), putchar('\n');
}