typical90_037.cpp

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
#include <atcoder/segtree>
//#define rep(i,a,n) for (int i=a;i<n;i++)
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0; i < (n); ++i)
#define rep2(i, n) for(ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
#define rrep(i,a,n) for (int i=n-1;i>=a;i--)
#define ALL(x) x.begin(),x.end()

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pause "read -p 'Press Enter to continue...' var"

using namespace std;
using namespace atcoder;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

/*
テスト通りますように
　　●
　　/⌒ヽ
　 ｜ 　|/⌒ヽ(ヽ
　 (｀　∥ー⌒) |
　|￣||￣￣￣￣￣|
　|―||―――――|
　|　Ｕ　　　　　|
　|￣￣￣￣￣￣￣|
　|＿＿＿＿＿＿＿|
　　|―――――|
　　|―――――|
ｗｗＷｗｗＷｗＷＷｗ
*/

typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;

//const ll INF = numeric_limits<ll>::max()/4;
const ll MAX = 200005;
const int MOD = 3;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

int main(){
  ll w,n;
  static ll dp[501][10005];
  vll vl,vr,vv;

  // 入力
  cin >> w >> n;
  rep(n){
    ll l,r,v;
    cin >> l >> r >> v;
    vl.pb(l);vr.pb(r);vv.pb(v);
  }

  // dp初期化
  rep(i,n+1){
    rep(j,w+1){
      dp[i][j] = -INF;
    }
  }

  // 最初の要素のdp処理
  dp[0][0] = 0;
  rep(i,vl[0],vr[0]+1) dp[0][i] = vv[0];

  // 最初のセグメント木作成処理
  vll v0;
  rep(i,w+1) v0.pb(dp[0][i]);
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(v0);

  // 残りの要素のdp処理
  rep(i,1,n+1){
    ll l,r,v;
    l = vl[i];
    r = vr[i];
    v = vv[i];
    rep(j,w+1){
      chmax(dp[i][j],dp[i-1][j]);
      ll left = j-r;
      if(left<0) left = 0;
      ll right = j-l;
      if(right<0) continue;
      chmax(dp[i][j],v + seg.prod(left,right+1));
    }
    rep(j,w+1) seg.set(j,dp[i][j]);
  }

  // 出力
  cout << max((ll)-1,dp[n-1][w]) << endl;
  return 0;
}