描述

John特别喜欢运动鞋，他喜欢收集各种品牌的运动鞋。现在商店里一共有n双运动鞋，他共有m元钱，这些运动鞋分为k类，每类都有自己的编号i，每类中的每双鞋有单价mi（同一类别的鞋价格也可以互不相同），John对每双鞋都有一个满意度vi。John想每一类运动鞋至少买一双，在不超过他所拥有的总金额前提下，使他得到的∑vi最大。

输入

第一行为三个正整数n(≤100),m(≤10000),k(≤10)，分别表示鞋的总数、John的总钱数和鞋的类别；接下来n行，每行三个正整数a(≤k),mi(≤10000),vi(≤10000)，分别描述每双鞋的类别、价钱和满意度。

输出

输出一个正整数，表示John能获得的满意度和的最大值，如果无法实现每种鞋购买至少一双，则输出"Impossible"

输入样例 1

5 10000 3

1 4 6

2 5 7

3 4 99

1 55 77

2 44 66

输出样例 1

255

输入样例 2

5 100 3

1 4 6

2 5 7

3 4 99

1 55 77

2 44 66

输出样例 2

189

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int m,v;
};
int n,m,k,ans,dp[10005],maxn=INT_MIN,minn=INT_MAX;
vector<node> a[15];
bool cmp(node x,node y)
{
	return x.m<y.m;
}
signed main()
{
	//freopen("string.in", "r", stdin);
	//freopen("string.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x].push_back(node{y,z});
	}
	for(int i=1;i<=k;i++)
	{
		sort(a[i].begin(),a[i].end(),cmp);
		ans+=a[i][0].m;
	}
	if(ans>m)
	{
		cout<<"Impossible\n";
		return 0;
	}
	for(int i=1;i<=k;i++)
	{
		for(int j=m;j>=0;j--)
		{
			for(auto z:a[i])
			{
				int m=z.m,v=z.v;
				dp[j]=max(dp[j],dp[j-m]+v);
			}
		}
	}
	cout<<dp[m]<<endl;
	return 0;
}
/*
*/

目前发现第一个样例会掠过前两个