#include<bits/stdc++.h>
using namespace std;
int n,m,t,c[1005],w[1005],f[1005],u[1005][1005];
int max(int a,int b){return a>b?a:b;}
int main(){
	cin>>m>>n>>t;
	for(int i=1;i<=n;i++){
		int x;
		cin>>w[i]>>c[i]>>x;
		u[x][++u[x][0]]=i;
	}
	for(int i=1;i<=t;i++)
		for(int j=m;j>=0;j--)
			for(int k=1;k<=u[i][0];k++){
				int kep=u[i][k];
				if(j<w[kep])break;
				else f[j]=max(f[j],f[j-w[kep]]+c[kep]);	
			}
	cout<<f[m];
	return 0;
}