#include <iostream>
#include <algorithm>
using namespace std;
int l,n,b;
//int x,w,f,c;
int F[1001][10001];
const int INF=10000000;
struct node
{
int x;
int w;
int f;
int c;
};
node Q[10001];
bool cmp(node a,node b)
{
if(a.x<b.x)
return 1;
return 0;
}
void dp()
{
int i,j,k;
for(k=0;k<n;k++)
{
i=Q[k].w+Q[k].x;
for(j=b;j>=Q[k].c;j--)
{
if(F[i][j]<F[i-Q[k].w][j-Q[k].c]+Q[k].f)
F[i][j]=F[i-Q[k].w][j-Q[k].c]+Q[k].f;
}
}
return ;
}
void init()
{
int i,j;
for( i=0;i<=b;i++)
{
F[0][i]=0;
}
for(j=1;j<=l;j++)
for(i=1;i<=b;i++)
F[j][i]=-INF;
}
int main()
{
scanf("%d%d%d",&l,&n,&b);
init();
for(int i=0;i<n;i++)
scanf("%d%d%d%d",&Q[i].x,&Q[i].w,&Q[i].f,&Q[i].c);
sort(Q,Q+n,cmp);
dp();
if(F[l][b]>0)
printf("%d\n",F[l][b]);
else
printf("-1\n");
return 0;
}