/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
整数 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 を満たす。
制約
- 入力は全て整数
- 1 \le N,M \le 4000
- 1 \le L_i \le R_i \le N
- 1 \le S_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
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 の総和としてありうる最小値を整数として出力せよ。
入力例 1
5 3 1 2 4 2 3 5 5 5 5
出力例 1
12
例えば、 A=(1,3,2,1,5) は問題文中の条件を満たします。
このとき A の総和は 12 で、これがありうる最小値です。
入力例 2
1 2 1 1 1 1 1 2
出力例 2
-1
問題文中の条件を満たす A が存在しないこともあります。
入力例 3
9 6 8 9 8 3 6 18 2 4 19 5 6 8 3 5 14 1 3 26
出力例 3
44
Score : 600 points
Problem Statement
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 ).
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
Input
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
Output
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 Input 1
5 3 1 2 4 2 3 5 5 5 5
Sample Output 1
12
For example, A=(1,3,2,1,5) satisfies the condition.
Its sum is 12, which is the minimum possible.
Sample Input 2
1 2 1 1 1 1 1 2
Sample Output 2
-1
Sometimes no such A exists.
Sample Input 3
9 6 8 9 8 3 6 18 2 4 19 5 6 8 3 5 14 1 3 26
Sample Output 3
44