本問は \(\mathrm{dp}_{i,j}\) を 「\(i\) 番目までの時間の科目を考えて、取得する単位が合計で \(j\) のときの労力の最小値(単位の合計が \(j\) になり得ない場合は十分大きな定数)」として動的計画法を行うことで解くことができます。
遷移はあらかじめ科目を \(b_i\) の値ごとにまとめ(解答例では9行目で宣言した \(p\) を用いている) 、時間の昇順にその時間の科目を履修しない場合とちょうど一つ履修する場合とを考慮します。
また、\(j\) は最大で \(5000^2\) まであり得ますが、\(M\) 以上の場合はすべて \(j=M\) として扱うものと出来ます。

解答例(C++)

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

int main() {
    
	int N,M;
	cin>>N>>M;
	
	vector<vector<pair<int,int>>> p(5000);
	
	vector<int> a(N),b(N),c(N);
	for(int i=0;i<N;i++){
		cin>>a[i]>>b[i]>>c[i];
		p[b[i]-1].emplace_back(a[i],c[i]);
	}
	
	vector dp(5001,vector<int>(M+1,1000000000));
	dp[0][0] = 0;
	
	for(int i=0;i<5000;i++){
		for(int j=0;j<=M;j++){
			dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
			for(int k=0;k<p[i].size();k++){
				int nj = min(M,j+p[i][k].second);
				dp[i+1][nj] = min(dp[i+1][nj],dp[i][j] + p[i][k].first);
			}
		}
	}
	
	int ans = dp[5000][M];
	
	if(ans==1000000000)ans = -1;
	
	cout<<ans<<endl;
	
	return 0;
}