看错题是你没有三七五的借口

由题很容易想到：背包、完全背包等。

看数据范围引导思考：按重量考虑。

重量的限制，让我联想到暴力多重背包：将所有物品拆分成一件一件相同的，再进行01背包。 本题也可以采取这种策略，将物品 $(w, v)$ 拆分成 $(w, v),(w, v-1),(w, v-2)\dots(w, v-\lfloor\frac{W}{w_i}\rfloor+1)$ 共 $\lfloor\frac{W}{w_i}\rfloor$ 个（继续拆分会填满背包，且必定更劣）。

显然这是正确的，因为即是我们在动态规划时取到了后续价值，结果也肯定不会比取实际价值优，这不会使答案变得错误。

如此做，在 $w_i$ 互不相同的情况下，最多会拆分出 $W\ln W$ 个物品，凭此可以通过特殊性质部分分。

进一步思考，我们可以将重量相同的物品放在一起考虑，也只共拆分出 $\lfloor\frac{W}{w_i}\rfloor$ 个。 显然，为保证最优性，我们应每次选取 $v$ 最大的物品取出，通过优先队列维护即可。

这样我们就又最多会拆分出 $W\ln W$ 个物品，直接套进01背包即可以 $O(W^2\ln W+W\log n)$ 的复杂度通过。

由于我们在拆分物品时将重量相同的物品都放在了一起，且是按价值从大到小排好的，所以有一个最优性剪枝：在枚举到一个物品无法再对答案做出贡献时，可以直接跳过剩下的同重量的物品。

核心代码：

ll w[3030], v[3030];
priority_queue<ll> c[3030];
for (int i = 1; i <= n; ++i)
	c[w[i]].pb(v[i]);
vector<pair<int, int>> a;
int nxt[3030];
for (int i = 1; i <= W; ++i) {
	for (int j = i; j <= W; j += i) {
		if (c[i].empty() || c[i].top() <= 0) break;
		a.pbb(c[i].top(), i);
		c[i].pb(c[i].top() - 1), c[i].pop();
	}
	nxt[i] = a.size();
}
ll f[3030];
for (int i = 0; i < a.size(); ++i) {
	bool g = 0;
	for (int j = W; j >= a[i].se; --j)
		if (f[j - a[i].se] + a[i].fi > f[j])
			f[j] = f[j - a[i].se] + a[i].fi,
			g = 1;
	if (!g)
		i = nxt[a[i].se] - 1;
}
ll ans = 0;
for (int j = 0; j <= W; ++j)
	ans = max(ans, f[j]);