刘宇轩题解。

不加 Markdown 不会写，洛谷题解写习惯了，就写带 $\LaTeX$ 的题解吧。

如果按这个思路感觉有点上位蓝了。

首先说结论。按以下式子排序后 $i$ 较小的更优：

$$s_i+w_i\le s_{i+1}+w_{i+1}$$

考虑证明。

看洛谷题解把这种贪心叫「微扰」，就是证明我们交换相邻两个数后一定不劣即可。

假设我们当前考虑 $i$ 和 $i+1$ 两个位置。

不交换时：

• $i$ 位置剩余的载重量：$$s_i-\sum_{j=1}^{i-1}w_j$$
• $i+1$ 位置剩余的载重量：$$s_{i+1}-\sum_{j=1}^{i}w_j$$

交换后：

• $i$ 位置剩余的载重量：$$s_i-\sum_{j=1}^{i-1}w_j-w_{i+1}$$
• $i+1$ 位置剩余的载重量：$$s_{i+1}-\sum_{j=1}^{i-1}w_j$$

不交换时对答案的贡献（仅考虑 $i$ 和 $i+1$）：

$$\min\{s_i-\sum_{j=1}^{i-1}w_j,s_{i+1}-\sum_{j=1}^{i}w_j\} $$

交换后对答案的贡献：

$$\min\{s_i-\sum_{j=1}^{i-1}w_j-w_{i+1},s_{i+1}-\sum_{j=1}^{i-1}w_j\} $$

把第一个记作 $\text{A}$ 式，第二个记作 $\text{B}$ 式。

我们只需要证明 $\text{A}\le\text{B}$，即可证明交换后答案不劣于交换前。

我们考虑枚举 $\text{A}$ 和 $\text{B}$ 的每一种情况。

为了方便观察，我们将 $\text{A}$ 和 $\text{B}$ 都加上：

$$\sum_{j=1}^{i+1}w_j$$

得到：

$$\text{A}=\min\{s_i+w_i+w_{i+1},s_{i+1}+w_{i+1}\}$$ $$\text{B}=\min\{s_i+w_i,s_{i+1}+w_i+w_{i+1}\}$$

分类讨论如下（$\text{A}\le\text{B}$）

• $\text{A}=s_i+w_i+w_{i+1}$，$\text{B}=s_i+w_i$

  由于 $\text{A}>\text{B}$，不满足假设条件，舍去。

• $\text{A}=s_{i+1}+w_{i+1}$，$\text{B}=s_i+w_i$

  因为我们假设 $\text{A}\le\text{B}$，故得到 $s_i+w_i≥ s_{i+1}+w_{i+1}$。

• $\text{A}=s_i+w_i+w_{i+1}$，$\text{B}=s_{i+1}+w_i+w_{i+1}$

  既然我们 $\text{B}=s_{i+1}+w_i+w_{i+1}$，又因为 $\text{B}=\min\{s_i+w_i,s_{i+1}+w_i+w_{i+1}\}$，故 $s_i+w_i≥s_{i+1}+w_i+w_{i+1}$，故 $s_i+w_i≥s_{i+1}+w_{i+1}$。

• $\text{A}=s_{i+1}+w_{i+1}$，$\text{B}=s_{i+1}+w_i+w_{i+1}$

  同上，交换 $\text{B}$ 的值，我们得到 $s_i+w_i≥s_{i+1}+w_{i+1}$。

故 $\text{A}\le\text{B}\Rightarrow s_i+w_i≥s_{i+1}+w_{i+1}$。

由该式，我们得到 $\text{A}=s_{i+1}+w_{i+1}$。

显然 $\text{B}$ 不论取哪个值，$\text{A}\le \text{B}$ 一直成立。

故 $s_i+w_i≥s_{i+1}+w_{i+1}\Rightarrow \text{A}\le\text{B}$。

故 $\text{A}\le\text{B}\Leftrightarrow s_i+w_i≥s_{i+1}+w_{i+1}$。

证毕。

#include <bits/stdc++.h>
using namespace std;
const int N = 30, M = (1 << 25) + 10;
int n, h, dp[M], ans = -1, x[M];//dp[i]表示i状态下的承受量; x[i]记录i状态下的高度 
struct node {
	int h, w, s;
} a[N];
bool cmp(node x, node y) {
	return x.w + x.s < y.w + y.s;//i较小的将更优 
}
int main() {
	scanf("%d%d", &n, &h);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &a[i].h, &a[i].w, &a[i].s);
	}
	sort(a + 1, a + n + 1, cmp);
	dp[0] = 1e9;//方便底下取min时，初始状态永远不会被转移到 
	for (int i = 1; i < (1 << n); i++) {
		int lst = __builtin_ffs(i);//取出i的第一个1，根据我们前面的推论，i较小的一定最优 
		x[i] = x[i ^ (1 << (lst - 1))] + a[lst].h;
		dp[i] = min(dp[i ^ (1 << (lst - 1))] - a[lst].w, a[lst].s);
		if (x[i] >= h) ans = max(ans, dp[i]);//如果dp是负数也没有关系，因为那代表不合法，不会影响ans的答案 
	}
	if (ans != -1) printf("%d", ans);
	else printf("Impossible");
	return 0;
}