唐突ですが、 \(\sum_{j=l}^{r} A_j = S_i\) という制約は扱いづらいため、 \(B(k) = \sum_{i=1}^{k} A_i\) と置き換えましょう。
すると、 \(\sum_{j=l}^{r} A_j = S_i\) という制約は \(B_{r} - B_{l-1} = S\) という形に置き換わります。

ここで、改めて数列に課されている制約を \(B\) を使って整理します。

• \(B_{R_i} - B_{L_i-1} = S_i\) ( \(1 \le i \le M\) )
• \(B_{j} - B_{j-1} \ge 1\) ( \(1 \le j \le N\) )

この制約を更に加工し、等号を不等号にします。

• \(B_{R_i} - B_{L_i-1} \ge S_i\) ( \(1 \le i \le M\) )
• \(B_{R_i} - B_{L_i-1} \le S_i\) ( \(1 \le i \le M\) )
• \(B_{j} - B_{j-1} \ge 1\) ( \(1 \le j \le N\) )

さて、解くべき問題は、次の線形計画問題として表現されます。

\[ \begin{aligned} &\text{minimize} & & B_N \\ &\text{subject to} & & B_{R_i} - B_{L_i-1} \ge S_i \ ( 1 \le i \le M ) \\ & & & B_{R_i} - B_{L_i-1} \le S_i \ ( 1 \le i \le M ) \\ & & & B_{j} - B_{j-1} \ge 1\ ( 1 \le j \le N ) \\ & & & B_0 = 0 \end{aligned} \]

ここで、全ての制約式が \(B_i + c \ge B_j\) の形で表現されることに注目します。これは特別な解きやすい形の線形計画問題で、 牛ゲー と呼ばれます。解説1 解説2 解説3 解説4 解説5
( これが 牛ゲー と呼ばれている理由は、このテクニックが浸透するに至った問題が「牛を並べる問題」であったからです。 移植1 移植2 )

牛ゲーそのものの目的関数は「特定の変数の最大化」ですが、線形計画問題を以下のように設定すれば問題ありません。
この問題の答えは以下の線形計画問題の最適解の目的関数の \(-1\) 倍となります。

\[ \begin{aligned} &\text{maximize} & & B_0 \\ &\text{subject to} & & B_{R_i} - B_{L_i-1} \ge S_i \ ( 1 \le i \le M ) \\ & & & B_{R_i} - B_{L_i-1} \le S_i \ ( 1 \le i \le M ) \\ & & & B_{j} - B_{j-1} \ge 1\ ( 1 \le j \le N ) \\ & & & B_N = 0 \\ \end{aligned} \]

あとは、この問題の形に従い適切なグラフを構築して Bellman-Ford 法で最短経路問題を解くと、この問題に正解できます。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n,m;
  cin >> n >> m;
  vector<long long> l(m),r(m),s(m);
  for(long long i=0;i<m;i++){
    cin >> l[i] >> r[i] >> s[i];
  }

  vector<array<long long,3>> eg;
  for(long long i=1;i<=n;i++){
    eg.push_back({i,i-1,-1});
  }
  for(long long i=0;i<m;i++){
    eg.push_back({r[i],l[i]-1,-s[i]});
    eg.push_back({l[i]-1,r[i],s[i]});
  }

  // for(auto &nx : eg){
  //   cout << nx[0] << " -> " << nx[1] << " : " << nx[2] << "\n";
  // }

  vector<long long> d(n+1,8e18);
  d[n]=0;
  bool upd;
  for(long long tr=0;tr<2*(n+m)+5;tr++){
    upd=false;
    for(auto &nx : eg){
      long long nd=d[nx[0]]+nx[2];
      if(d[nx[1]] > nd){
        d[nx[1]]=nd;
        upd=true;
      }
    }
  }
  
  if(upd){cout << "-1\n"; return 0;}
  cout << -d[0] << "\n";
  return 0;
}