¡¾À§»ó¡¿uva301 Ò»Ö±TLE°¡ÔõôÆÆ£¡

#include<iostream>
#include<cstring>

using namespace std;

struct Order
{
 int sta,des,num;
};
int capacity,Bstation,norder,Max,stapass[8];
bool vis[23];
Order order[23];

bool isok(int ord)
{
 for (int i=order[ord].sta;i<order[ord].des;i++)
  if (stapass[i]+order[ord].num>capacity)
   return 0;
 return 1;
}
void addpass(int ord)
{
 for (int i=order[ord].sta;i<order[ord].des;i++)
  stapass[i]=stapass[i]+order[ord].num;
}
void deletepass(int ord)
{
 for (int i=order[ord].sta;i<order[ord].des;i++)
  stapass[i]=stapass[i]-order[ord].num;
}
int getmoney(int ord)
{
 return order[ord].num*(order[ord].des-order[ord].sta);
}
void dfs(int earning)
{
 int i;
 if (earning>Max) Max=earning;
 for (i=0;i<norder;i++)
 {
  if (!vis[i]&&isok(i))
  {
   vis[i]=1;
   addpass(i);
   int earn=getmoney(i);
   dfs(earning+earn);
   vis[i]=0;
   deletepass(i);
  }
 }
 
}
int main()
{
 while (cin>>capacity>>Bstation>>norder&&capacity)
 {
  for (int i=0;i<norder;i++)
   cin>>order[i].sta>>order[i].des>>order[i].num;
  Max=0;
  memset(stapass,0,sizeof(stapass));
  memset(vis,0,sizeof(vis));
  dfs(0);
  cout<<Max<<endl;
 }
 return 0;
}