rt，普通背包+颜色，不知为何大样例是错的。

#include <cstdio>
#define int long long int

const int N = 505, X = 5e4 + 5;
int n, x, k, p[N], u[N], c[N], dp[X];
bool vis[N][N];

signed main(void)
{
	scanf("%lld %lld %lld", &n, &x, &k);
	
	for (int i = 0; i < n; i++)
	{
		scanf("%lld %lld %lld", &p[i], &u[i], &c[i]);
	}
	
	for (int i = 0; i < n; i++)
	{
		for (int j = x; j >= 0; j--)
		{
			if (j >= p[i])
			{
				if (dp[j] < dp[j - p[i]] + u[i] + (!vis[j - p[i]][c[i]]) * k)
				{
					dp[j] = dp[j - p[i]] + u[i] + (!vis[j - p[i]][c[i]]) * k;
					
					for (int d = 0; d < n; d++)
					{
						vis[j][d] = vis[j - p[i]][d];
					}
					
					vis[j][c[i]] = true;
				}
			}
		}
	}
	
	printf("%lld", dp[x]);
	return 0;
}