Description

【题意】
有 $N$ 头奶牛，第i头奶牛的身高为 $H_i$ ，重量为 $W_i$ ，力量为 $S_i$ 。
从中选出一部分奶牛，让其中一头站在地上，剩下的奶牛挨个爬到前一头的背上。
要求每头奶牛的力量大于或等于压在它身上的奶牛重量之和。
总高度只要大于或等于 $H$ 就足够了。
如果有多个方案能达到要求，输出最上面那头牛的头顶能增加的重量最大的那个方案。

【输入格式】
第一行：两个整数 $N$ 和 $H$ ，$1 \le N \le 20,1 \le H \le 10^9$
第二行到第 $N+1$ 行：第 $i+1$ 行有三个整数 $H_i$ , $W_i$ 和 $S_i$ ，$1 \le H_i,W_i,S_i \le 10^9$

【输出格式】
如果存在超过或达到高度 $H$ 的方案，输出最上面那头牛的头顶能增加的重量的最大值；
否则输出一行字“Mark is too tall”

【样例输入】
4 10 
9 4 1 
3 3 5 
5 5 10 
4 4 5 

【样例输出】
2

Hint

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=22;
typedef long long LL;
struct node{LL h, w, e;} a[N];
LL f[(1<<N)], g[(1<<N)];
int main(){
	int n; LL H; scanf("%d%lld", &n, &H);
	for(int i=1; i<=n; i++) 
		scanf("%lld%lld%lld", &a[i].h, &a[i].w, &a[i].e);
	memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g));
	for(int i=1; i<=n; i++){
		f[1<<(i-1)]=a[i].e; 
		g[1<<(i-1)]=a[i].h;
	}
	LL ans=0; 
	for(int i=0; i<(1<<n); i++){
		for(int j=1; j<=n; j++) if(i&(1<<(j-1))){
			int x=i^(1<<(j-1)); LL d=min(a[j].e, f[x]-a[j].w);
			if((d>f[i]) || (d==f[i] && g[x]+a[j].h>g[i])){
				f[i]=d; g[i]=g[x]+a[j].h;
				if(g[i]>=H) ans=max(ans, f[i]);
			}
		}
	}
	if(ans==0) printf("Mark is too tall\n");
	else printf("%lld\n", ans);
	return 0;
}