今晚F不过样例求调:

# include <bits/stdc++.h>

# define I return

# define AK 0

# define IOI ;

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

struct node {

	int y, k;

	ll v;

	bool operator < (const node& a) const {

		return v < a.v;

	}

} ;

int n, m, x, y;

ll dp[3005], a[3005][3005];

priority_queue <node> q[3005];

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	cin >> n >> m;

	while (n --)
		cin >> x >> y, q[x].push ({y, 1, y - 1});

	for (int i = 1; i <= m; ++ i)
		if (! q[i].empty ())
			for (int j = 1; j * i <= m; ++ j) {

				node x = q[i].top ();

				q[i].pop ();

				a[i][j] = x.v + a[i][j - 1];
//				cerr << i << ',' << j << ':' << a[i][j] << '\n';
				++ x.k, x.v = x.k * (ll) (x.y - x.k) - x.v;

				q[i].push (x);

			}

	for (int i = 1; i <= m; ++ i)
		if (! q[i].empty ()) //{
			for (int j = m; j; -- j)
				for (int k = 1; k * i <= j; ++ k)
					dp[j] = max (dp[j], dp[j - k * i] + a[i][k]);
//			for (int j = 1; j <= m; ++ j) cerr << i << ',' << j << ':' << dp[j] << '\n';
//		}

	cout << dp[m];

	I AK IOI

}

How F

捞