#include<bits/stdc++.h>#define inf 1000000007using namespace std;int d,g,ans;bool f;struct sd{int t,f,h;bool operator < (const sd q) const{return t<q.t;};}s[1009];int dp[2][109],q[109];int main(){scanf("%d%d",&d,&g);for(int i=1;i<=g;i++){scanf("%d%d%d",&s[i].t,&s[i].f,&s[i].h);}sort(s+1,s+g+1);for(int j=0;j<=105;j++) dp[0][j]=-inf;dp[0][0]=10;s[g+1].t=inf;memset(q,-1,sizeof(q));for(int i=1;i<=g;i++){for(int j=0;j<=105;j++){q[j+s[i].h]=max(dp[(i-1)&1][j],q[j+s[i].h]);q[j]=max(q[j],dp[(i-1)&1][j]+s[i].f);}f=0;for(int j=d;j<=105;j++){if(q[j]>=0){printf("%d\n",s[i].t);return 0;}}for(int j=0;j<=105;j++){dp[i&1][j]=q[j];if(q[j]>=s[i+1].t) f=1;else dp[i&1][j]=-inf;}if(!f){for(int j=0;j<=105;j++) if(ans<q[j]) ans=q[j];printf("%d\n",ans);return 0;}memset(q,-1,sizeof(q));}for(int i=1;i<=105;i++){if(dp[g&1][i]>ans) ans=dp[g&1][i];}printf("%d\n",ans);return 0;}

#include<bits/stdc++.h>using namespace std;int n,to[22][22],ans,vis[22];char s[22][1000];bool f=0;void dfs(int b,int x){    if(x>ans) ans=x;    for(int i=1;i<=n;i++){        if(to[b][i]&& (vis[i]<2)) {            vis[i]++;            dfs(i,x+strlen(s[i])-to[b][i]);            vis[i]--;        }    }}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%s",s[i]);    }    scanf("%s",s[0]);    for(int i=0;i<=n;i++){        for(int j=0;j<=n;j++){            for(int k=strlen(s[i])-1;k>=0;k--){f=0;                for(int q=k;q<strlen(s[i]);q++){                    if(s[i][q]!=s[j][q-k]) f=1;                }                if(!f){                    to[i][j]=strlen(s[i])-k;                    break;                }            }        }    }    vis[0]=2;    dfs(0,1);    printf("%d\n",ans);    return 0;}

#include<bits/stdc++.h>using namespace std;int n,dp[2005][5];int main(){    freopen("x.in","r",stdin);    freopen("x1.out","w",stdout);    scanf("%d",&n);    dp[1][1]=1;int s=n/2;if(n%2) s++;    for(int i=2;i<=n;i++)    for(int j=1;j<=4;j++){        dp[i][j]=dp[i-1][j]+dp[i-1][j-1];        if(i>=(s+j-1)&&j>1) dp[i][j]-=dp[i-s][j-1];        if(i>=(s+j-1)&&j==1) dp[i][j]--;        if(dp[i][j]<0) dp[i][j]=0;    }    printf("%d\n",dp[n][4]);    return 0;}

#include<bits/stdc++.h>#define maxn 2505#define inf 10000000000000000#define ll long long//记得看范围 using namespace std;ll n,m[maxn],dp[maxn];int main(){    scanf("%lld%lld",&n,&m[0]);    for(int i=1;i<=n;i++){        scanf("%lld",&m[i]);        m[i]+=m[i-1];dp[i]=inf;    }    dp[0]=0;    for(int i=0;i<=n;i++){        for(int j=1;j+i<n;j++){            dp[i+j]=min(dp[i+j],dp[i]+m[j]+m[0]);        }        dp[n]=min(dp[n],dp[i]+m[n-i]);    }    printf("%lld\n",dp[n]);}

#include<bits/stdc++.h>using namespace std;int n,dp[2][155][2],k,ans;int main(){    scanf("%d%d",&n,&k);int a;scanf("%d",&a);    dp[1][1][a]=1;    for(int p=0,q=1,i=1;i<n;i++,swap(p,q)){        scanf("%d",&a);        for(int j=1;j<=2*k-1;j++)        for(int x=0;x<2;x++)        for(int y=0;y<2;y++){            dp[p][j+(x!=y)][y]=max(dp[q][j][x]+(y==a),dp[p][j+(x!=y)][y]);            //记得把相同的放前面，改自己代码之前先想一想         }        for(int j=1;j<=2*k-1;j++){            ans=max(ans,dp[p][j][0]);ans=max(ans,dp[p][j][1]);            dp[q][j][0]=dp[q][j][1]=0;        }    }    printf("%d\n",ans);    return 0;}