この問題は、各ビタミン \(i\) \((1\leq i\leq 3)\) について、「摂取カロリーの合計が \(j\) \((0\leq j\leq X)\) 以下となるように食べ物を選んで食べた時のビタミン \(i\) の摂取量の最大値（他のビタミンについては考慮しない）」を動的計画法によって、あらかじめ求めておくことによって解くことができます。

最初に、「摂取カロリーの合計が ちょうど \(j\) となるように食べ物を選んで食べた時のビタミン \(i\) の摂取量の最大値」の計算を行います。
\(dp_i[k][j]\) \((1\leq i\leq 3,~0\leq j\leq X,~0\leq k\leq N)\) で、「\(1\) 個目から \(k\) 個目までの食べ物の中から摂取カロリーの合計が ちょうど \(j\) となるように食べ物を選んで食べた時のビタミン \(i\) の摂取量の最大値（できない場合は\(-\infty\)）」を表すとします。
まず、\(dp_i[0][0]=0\), \(dp_i[0][j]=-1\) \((1\leq j\leq X)\) です。
次に、食べ物 \(k\) \((1\leq k\leq N)\) がビタミン \(i\) を含まないならば \(dp_i[k][j]=dp_i[k-1][j]\) です。含むならば、食べるか食べないかの選択によって、\(dp_i[k][j]=\max(dp_i[k-1][j],dp_i[k-1][j-C_k]+A_k)\) \((C_k\leq j)\) となります。\(j\leq c_k\) については \(dp_i[k][j]=dp_i[k-1][j]\) となります。
このように更新を繰り返した時の、\(dp_i[N][j]\) が求めたいものです。

次に、「摂取カロリーの合計が \(j\) \((0\leq j\leq X)\) 以下となるように食べ物を選んで食べた時のビタミン \(i\) の摂取量の最大値」\(M_{i,j}\) は、\(M_{i,j}=\displaystyle\max_{0\leq j'\leq j} dp_i[N][j']\) と書くことができます。 これは、\(M_{i,0}=dp_i[N][0]\), \(M_{i,j}=\max(M_{i,j-1},dp_i[N][j])\) として逐次的に計算することができます。

最後に、ビタミン \(i\) \((1\leq i\leq 3)\) の摂取のために食べる食べ物のカロリーの合計が \(s_i\) 以下である時の 「ビタミン \(1,2,3\) のうちもっとも摂取量が少ないものの摂取量」は \(\min(M_{1,s_1}, M_{2,s_2}, M_{3,s_3} )\) で与えられるため、求めたい値は

\[ \max_{s_1+s_2+s_3=X} \min(M_{1,s_1}, M_{2,s_2}, M_{3,s_3} ) \]

です。\( \min(M_{1,s_1}, M_{2,s_2}, M_{3,s_3} )\) を最大化する組み合わせ \((s_1,s_2,s_3)=(S_1,S_2,S_3)\) は貪欲法によって、求めることができます。
具体的には、\(S_1=S_2=S_3=0\) から始めて次の操作をちょうど \(X\) 回繰り返します。

\(M_{1,S_1}\), \(M_{2,S_2}\), \(M_{3,S_3}\) を比較する。
その中で一番小さいものが \(M_{i,S_i}\) であったとき、\(S_i\) を \(1\) 増加させる。
最も小さいものが複数ある場合はその中からどれを選んでも良い。

求まった \((S_1,S_2,S_3)\) に対する値 \(\min(M_{1,S_1}, M_{2,S_2}, M_{3,S_3} )\) が最終的な答えとなります。
時間計算量は全体で \(O(NX)\) であり、十分高速です。
よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

#define M 5000
#define INF (int)2e+9

int main(void){
	int n,x,v,a,c;
	int dp[3][M+1]={};
	for(int i=0;i<3;i++){
		for(int j=0;j<M;j++){
			dp[i][j+1]=-INF;
		}
	}

	cin>>n>>x;
	for(int i=0;i<n;i++){
		cin>>v>>a>>c;
		for(int j=x;j>=c;j--){
			dp[v-1][j]=max(dp[v-1][j],dp[v-1][j-c]+a);
		}
	}
	for(int i=0;i<3;i++){
		for(int j=0;j<x;j++){
			dp[i][j+1]=max(dp[i][j],dp[i][j+1]);
		}
	}

	int idx[3]={0,0,0};
	for(int i=0;i<x;i++){
		if((dp[0][idx[0]]<=dp[1][idx[1]])&&(dp[0][idx[0]]<=dp[2][idx[2]]))idx[0]++;
		else if((dp[1][idx[1]]<=dp[0][idx[0]])&&(dp[1][idx[1]]<=dp[2][idx[2]]))idx[1]++;
		else idx[2]++;
	}
	cout<<min(dp[0][idx[0]],min(dp[1][idx[1]],dp[2][idx[2]]))<<endl;
	return 0;
}