下面的代码是错误的：硬是检查不出啦那里错了，样例能过
http://archive.cnblogs.com/a/1783879/这里讲的很详细，，，，
//每一组内至少取一件
/*
程序思想：f[i][j]代表用j的价钱买前i个品牌可以得到的最大价值数。
赋初值：见18到22行
状态转移：f[i][j]可以经过三种状态得到————
f[i][j]，f[i-1][j-p[br[i][i1]]]+v[br[i][i1]]，f[i][j-p[br[i][i1]]]+v[br[i][i1]]
br[i][i1]代表第i种品牌的第i1个产品，p[]是某产品的价格，v[]是某产品的价值。
意思是，当放到第i个品牌的第i1个产品时，它的状态等于不放第i1个产品，而放i1
以前的i类品牌中的某些产品（f[i][j]），放i类品牌的第i1个产品，而不放i的其他
产品（f[i-1][j-p[br[i][i1]]]+v[br[i][i1]]），放i类的第i1个产品，同时也放i类中i1以前
的某些产品 （f[i][j-p[br[i][i1]]]+v[br[i][i1]] ） 。
几个问题：
1.如何保证每一类品牌至少放一件产品？
答：首先看循环:
for(i=1;i<=k;i++)
for(i1=1;i1<=sum[i];i1++)
for(j=m;j>=1;j--)
if(j>=p[br[i][i1]])----限制条件
在某一状态存在的情况下（不等于-1），找出三种状态中最大的，赋值给f[i][j] .
由于开始时所有f[i][j](i!=0)都为-1，所以i=1
更新时一定会从f[0][]开始，而此时就可保证当i=1时，f[i][j]中所有值不为-1的状
态一定装了品牌1的某个物品。而当i>1时，
要想得到最初的f[i][j],一定是从已经放有前i-1个品牌的某个状态得到的，而更新
最初的f[i][j] 也一定会用到i品牌的某
个产品(都可由状态转移方程可知)。
总之，保证每一类品牌 至少放一件产品是通过赋初值，条件判断，状态转移三方面实现的。
2.如何抱证每个产品只放一次？
答： 注意循环安排顺序：将对某一品牌产品编号的循环放在对限制总钱数的循环之前 。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
int a,p,v;
}arr[200];
int cmp(node x,node y)
{
return x.a<y.a;
}
__int64 dp[20][20000];//dp[i][j]用钱j买前i种品牌，所得的最大价值
int main()
{
int n,m,k;
while(scanf("%d %d %d",&n,&m,&k)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d %d %d",&arr[i].a,&arr[i].p,&arr[i].v);
sort(arr+1,arr+1+n,cmp);
/*for(int i=1;i<=n;i++)
printf("%d %d %d***\n",arr[i].a,arr[i].p,arr[i].v);*/
memset(dp,-1,sizeof(dp));
memset(dp[0],0,sizeof(dp[0]));
int amount,p=1,head;
for(int i=1;i<=k;i++)
{
amount=1;
head=p;
while(arr[p].a==arr[p+1].a)
{
amount++;
p++;
}
p++;
//printf("head=%d tail=%d****\n",head,head+amount-1);
for(int j=head;j<=head+amount-1;j++)
for(int t=m;t>=arr[j].p;t--)///变量重名了，刚用了k
{//dp[i][t]来源于：dp[i][t],dp[i][t-arr[j].p]+arr[j].v,
//和dp[i-1][t-arr[j].p]+arr[j].v
if(dp[i][t-arr[j].p]!=-1)
dp[i][t]=max(dp[i][t],dp[i][t-arr[j].p]+arr[j].v);
if(dp[i-1][t-arr[j].p]!=-1)
dp[i][t]=max(dp[i][t],dp[i-1][t-arr[j].p]+arr[j].v);
}
}
if(dp[k][m]<0)
printf("Impossible\n");
else
printf("%I64d\n",dp[k][m]);
}
system("pause");
return 0;
}