> # include <stdio.h>
> typedef struct point 
> {
>   int price;
>   int p;
>   int s;
>   int e;
> }sta;
> sta data[23];  
> int station[8];
> int maxnum,stanum,ticnum;
> int tres,res;
> check(int s)
> {
>  int i;
>  for(i=data[s].s;i<data[s].e;i++)
>    if(station[i]+data[s].p>maxnum) return 0;
>  return 1;
> }
> void deal(int s)
> {
>  if(s>ticnum&&tres>res) res=tres;
>  else if(s>ticnum) return;
>  else
>  {
>      int i;
>      if(check(s))
>      {
>       for(i=data[s].s;i<data[s].e;i++) station[i]+=data[s].p;
>       tres+=data[s].price;
>       deal(s+1);
>       for(i=data[s].s;i<data[s].e;i++) station[i]-=data[s].p;
>       tres-=data[s].price;
>      }
>      deal(s+1);
>  }
> }
>  
> int main()
> {
> 
>     while(1)
>     {
>       int i,j,totalp=0; 
>       memset(station,0,sizeof(station));
>       scanf("%d %d %d",&maxnum,&stanum,&ticnum);
>       if(!maxnum&&!stanum&&!ticnum) break;
>       for(i=1;i<=ticnum;i++)
>       {
>        scanf("%d %d %d",&data[i].s,&data[i].e,&data[i].p);
>        data[i].price=data[i].p*(data[i].e-data[i].s);
>       }
>        res=tres=0;
>        deal(1);
>        
>        printf("%d\n",res);
>      }
>    
>      return 0;
> }
>