一、题目简述

有 $m$ 个馒头，每个价格 $p_i$；有 $n$ 种盒子，每种容量 $C_j$ 和价格 $E_j$，每种盒子最多买一个。 你可以选一些盒子，把馒头装进去（每个盒子装不超过容量的任意数量），按馒头总价卖出。 利润 = 卖出总价 - 盒子总价，没装盒的馒头不算。 求最大利润。

二、解题思路

馒头价格不同，肯定优先卖最贵的。 先把馒头价格从大到小排序，并算出前缀和 $pre_i$ 表示前 $i$ 个最贵馒头的总价。

问题变成：选一些盒子，使总容量至少为 $x$（$x$ 从 $0$ 到 $m$），并让盒子总成本最小，利润就是 $pre_x - \text{最小成本}$，取最大值。

1. 用背包求最小成本 设 $dp_c$ 表示总容量 恰好 为 $c$ 的最小盒子总价（$0 \le c \le m$）。 初始化 $dp_0=0$，其余为无穷大。 对每个盒子（容量 $c$，价格 $e$），令有效容量 $c = \min(C_j, m)$。 因为是 01 背包，我们从 $m$ 向下循环 $j$，用旧 $dp_j$ 更新新容量：

新容量 $t = \min(j + c, m)$

$dp_t = \min(dp_t, dp_j + e)$

这样就能把总容量超过 $m$ 的情况也归结到 $dp_m$ 里。

2. 转为至少容量 计算后缀最小值 $suff_x = \min_{t \ge x} dp_t$，表示总容量至少为 $x$ 的最小成本。 如果 $suff_x$ 无穷大，说明无法装 $x$ 个馒头。

3. 计算答案 枚举 $x = 0 \dots m$，若 $suff_x$ 有限，则利润为 $pre_x - suff_x$，取最大值。 注意不买盒子时 $x=0$ 利润为 $0$。

三、代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXM = 10005;
const int INF = 1e18;

int m, n;
int p[MAXM];
int pre[MAXM];
int dp[MAXM];

signed main() {
	cin.tie(0)->ios::sync_with_stdio(false);
	cin >> m >> n;
	for (int i = 1; i <= m; ++i) cin >> p[i];
	sort(p + 1, p + m + 1, greater<int>());
	pre[0] = 0;
	for (int i = 1; i <= m; ++i) pre[i] = pre[i-1] + p[i];
	for (int i = 0; i <= m; ++i) dp[i] = INF;
	dp[0] = 0;
	for (int j = 0; j < n; ++j) {
		int c, e;
		cin >> c >> e;
		c = min(c, m);
		for (int k = m; k >= 0; --k) {
			if (dp[k] == INF) continue;
			int t = min(k + c, m);
			dp[t] = min(dp[t], dp[k] + e);
		}
	}
	// 后缀最小值
	for (int i = m-1; i >= 0; --i) {
		dp[i] = min(dp[i], dp[i+1]);
	}
	int ans = 0;
	for (int x = 0; x <= m; ++x) {
		if (dp[x] < INF) {
			ans = max(ans, pre[x] - dp[x]);
		}
	}
	cout << ans << "\n";
	return 0;
}