Untitled

//#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define MAXITEMS 105
#define MAXKNAPSIZE 10005
typedef struct s
{
	int item,value,size,qty;
	int fincnt;
}Item;

int N,A,B;
Item array[MAXITEMS],copy[MAXITEMS];
Item save[MAXITEMS];
int cost[MAXKNAPSIZE],prev[MAXKNAPSIZE],best[MAXKNAPSIZE],count[MAXKNAPSIZE];

int compare(const void* a, const void* b) // based on size
{
	if( (*(Item*)a).size > (*(Item*)b).size )
		return 1;
	else if( (*(Item*)a).size < (*(Item*)b).size )
		return -1;
	return 0;
}
int comp(const void* a, const void* b) //based on item id
{
	if( (*(Item*)a).item > (*(Item*)b).item )
		return 1;
	else if( (*(Item*)a).item < (*(Item*)b).item )
		return -1;
	return 0;
}

FILE *fp;
void trace()
{
	int i;
	fp = stdout;
	for(i=1;i<=B;i++)
		fprintf(fp,"%d ",cost[i]);
	fprintf(fp,"\n\n");
	for(i=1;i<=B;i++)
			fprintf(fp,"%d ",prev[i]);
	fprintf(fp,"\n\n");
	for(i=1;i<=B;i++)
		fprintf(fp,"%d ",best[i]);
	fprintf(fp,"\n\n");
	for(i=1;i<=B;i++)
		fprintf(fp,"%d ",count[i]);
	fprintf(fp,"\n\n");
}
int main()
{
	int i,j,k,M,sum=0,max=0,masssum=0,flag=0,p=0,mx=0;
	//clrscr();
	scanf("%d %d %d",&N,&A,&B);
//	fp = fopen("knap.txt","w");
	M=B;
	for(i=1;i<=N;i++)
	{
		array[i].item = i;
		array[i].fincnt = 0;
		scanf("%d %d %d",&array[i].value,&array[i].size,&array[i].qty);
		masssum += (array[i].value*array[i].qty);
	}
	for(i=1;i<=N;i++)
	{
		if(array[i].size<=B)
		{
			flag=1;
			break;
		}
	}
	if(flag==0||masssum<A)
	{
		printf("-1\n");
		return 0;
	}
	qsort(array,N+1,sizeof(Item),compare);
	for(j=1;j<=N;j++)
	{
		for(i=array[j].size;i<=M;i++)
		{
			int X = cost[i-array[j].size] + array[j].value;
			if(cost[i]<X)
			{
				p = best[i-array[j].size]==j?count[i-array[j].size]:0;
				if(p+1<=array[j].qty)
				{
					cost[i] = X;
					prev[i] = i-array[j].size;
					best[i] = j;
					count[i] = p+1;
				}
				else
				{
					if(cost[i-1]>cost[i-array[j].size])
						mx = i-1;
				    else
						mx = i-array[j].size;
					cost[i] = cost[mx];
					prev[i] = prev[mx];
					best[i] = best[mx];
					count[i] = count[mx];
				}
			}
		}
		//trace();
		//printf("\n Iteration Over!!");
		//getch();
	}
  
	for(k=B;k>=A;k--)
	{
		sum = 0;
		for(i=1;i<=N;i++)
			array[i].fincnt=0;
		for(i=k;;i=prev[i])
		{
			array[best[i]].fincnt++;
			if(prev[i]==0)
				break;
		}
		for(i=1;i<=N;i++)
			sum += (array[i].value*array[i].fincnt);

		if(sum>max)
		{
			max=sum;
			for(p=1;p<=N;p++)
				save[p] = array[p];
		}
	}
	if(max>0)
	{
		printf("%d\n",max);
		qsort(save,N+1,sizeof(Item),comp);
		for(i=1;i<=N;i++)
			printf("%d\n",save[i].fincnt);
	}
	else
		printf("-1\n");
	return 0;
}