AT_abc404_g [ABC404G] Specified Range Sums

You are given an integer $ N $ and length- $ M $ integer sequences $ L=(L_1,L_2,\dots,L_M) $ , $ R=(R_1,R_2,\dots,R_M) $ , and $ S=(S_1,S_2,\dots,S_M) $ . Determine whether there exists a length- $ N $ **positive integer sequence** $ A $ satisfying the following condition. If such a sequence exists, find the minimum possible sum of $ A $ . - $ \displaystyle \sum_{j=L_i}^{R_i} A_j = S_i $ for all $ i $ ( $ 1 \le i \le M $ ).

The input is given from Standard Input in the following format: > $ N $ $ M $ $ L_1 $ $ R_1 $ $ S_1 $ $ L_2 $ $ R_2 $ $ S_2 $ $ \vdots $ $ L_M $ $ R_M $ $ S_M $

If there does not exist a length- $ N $ positive integer sequence $ A $ satisfying the condition, print `-1`. Otherwise, print the minimum possible sum of $ A $ as an integer.

### Sample Explanation 1 For example, $ A=(1,3,2,1,5) $ satisfies the condition. Its sum is $ 12 $ , which is the minimum possible. ### Sample Explanation 2 Sometimes no such $ A $ exists. ### Constraints - All input values are integers. - $ 1 \le N,M \le 4000 $ - $ 1 \le L_i \le R_i \le N $ - $ 1 \le S_i \le 10^9 $