> #include<iostream>
> #include<algorithm>
> #include<stdio.h>
> #include<string.h>
> #include<stdlib.h>
> 
> using namespace std;
> 
> int map[25][25];
> int mm[25][25];
> int v[25][25];
> int n,m,w;
> int maxx;
> int pi;
> 
> void DFS(int sum,int pw)
> {
>     //printf("sum = %d       pw = %d\n",sum,pw);
>     for(int i=0; i<=n; i++)
>     {
>         for(int j=i+1; j<=n; j++)
>         {
>             if(v[i][j] == 1)
>             {
>                 continue;
>             }
>             if(map[i][j]!=0 && i>=pi)
>             {
>                 for(int k=0; k<n; k++)
>                 {
>                     for(int kk=0; kk<=i; kk++)
>                     {
>                         if(v[k][kk] == 1)
>                         {
>                             pw += mm[k][kk];
>                             mm[k][kk] = 0;
>                         }
>                     }
>                 }
>                 if(pw-map[i][j]>=0)
>                 {
>                     mm[i][j] = map[i][j];
>                     if(pi < i)
>                     {
>                         pi = i;
>                     }
>                     //printf("pw = %d          v[%d][%d] = 1\n",pw,i,j);
>                     v[i][j] = 1;
>                     //printf("pw = %d\n",pw-map[i][j]);
>                     DFS((sum+((j-i)*map[i][j])),pw-map[i][j]);
>                     v[i][j] = 0;
>                    // printf("***pw = %d               v[%d][%d] = 0\n",pw,i,j);
>                 }
> 
>             }
>         }
>     }
>     if(maxx<sum)
>     {
>         maxx = sum;
>         //return ;
>     }
> }
> 
> int main()
> {
>     while(scanf("%d%d%d",&w,&n,&m)!=EOF)
>     {
>         if(w == 0 && n == 0 && m == 0)
>         {
>             break;
>         }
>         maxx = 0;
>         memset(map,0,sizeof(map));
>         memset(v,0,sizeof(v));
>         memset(mm,0,sizeof(mm));
>         int px,py,pz;
>         pi = 0;
>         for(int i=0; i<m; i++)
>         {
>             scanf("%d%d%d",&px,&py,&pz);
>             map[px][py] = pz;
>         }
>         DFS(0,w);
>         printf("%d\n",maxx);
>     }
>     return 0;
> }