AT_abc404_g [ABC404G] Specified Range Sums

整数 $ N $ と長さ $ M $ の整数列 $ L=(L_1,L_2,\dots,L_M),R=(R_1,R_2,\dots,R_M),S=(S_1,S_2,\dots,S_M) $ が与えられるので、次の問題を解いてください。 以下の条件を満たす長さ $ N $ の **正整数列** $ A $ が存在するか判定し、存在する場合は $ A $ の総和としてありうる最小値を求めてください。 - 全ての $ i $ ( $ 1 \le i \le M $ ) について、 $ \displaystyle \sum_{j=L_i}^{R_i} A_j = S_i $ を満たす。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L_1 $ $ R_1 $ $ S_1 $ $ L_2 $ $ R_2 $ $ S_2 $ $ \vdots $ $ L_M $ $ R_M $ $ S_M $

問題文中の条件を満たす長さ $ N $ の正整数列 $ A $ が存在しない場合、 `-1` と出力せよ。 そうでない場合、 $ A $ の総和としてありうる最小値を整数として出力せよ。

### Sample Explanation 1 例えば、 $ A=(1,3,2,1,5) $ は問題文中の条件を満たします。 このとき $ A $ の総和は $ 12 $ で、これがありうる最小値です。 ### Sample Explanation 2 問題文中の条件を満たす $ A $ が存在しないこともあります。 ### Constraints - 入力は全て整数 - $ 1 \le N,M \le 4000 $ - $ 1 \le L_i \le R_i \le N $ - $ 1 \le S_i \le 10^9 $