我们考虑从前往后和从后往前进行线性DP，得到 $f_{i,j}$ 为游玩前 $i$ 个游乐设施，花费 $j$ 元的最大快乐值； $g_{i,j}$ 为游玩后 $i$ 个游乐设施，花费 $j$ 元的最大快乐值。

那么对于兔儿子想要游玩的第 $idx$ 个游乐设施，当 $c_{idx} > k$ 时无解；反之我们可以枚举游玩前 $i$ 个游乐设施的开销 $g$ 进行计算答案：

$$ans = \mathop{\max}_{0 \leq g \leq k-c_{idx}} f_{idx-1,g}+ h_{idx}+ g_{idx+1,k-g-c_{idx}} $$

时间复杂度：$O(n^2)$

const int maxn = 2e3 + 7;
int n, k, q, h[maxn], c[maxn];
int f[maxn][maxn], d[maxn][maxn];

void solve()
{
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++)
		cin >> h[i] >> c[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
			f[i][j] = f[i - 1][j];
		for (int j = c[i]; j <= k; j++)
			f[i][j] = max(f[i][j], f[i - 1][j - c[i]] + h[i]);
	}

	for (int i = n; i >= 1; i--)
	{
		for (int j = 0; j <= k; j++)
			d[i][j] = d[i + 1][j];
		for (int j = c[i]; j <= k; j++)
			d[i][j] = max(d[i][j], d[i + 1][j - c[i]] + h[i]);
	}

	while (q--)
	{
		int x;
		cin >> x;
		if (c[x] > k)
		{
			cout << -1 << endl;
			continue;
		}

		int ans = h[x];
		for (int i = 0; i <= k - c[x]; i++)
			ans = max(ans, h[x] + f[x - 1][i] + d[x + 1][k - c[x] - i]);
		cout << ans << endl;
	}
}