分数: 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.
- \displaystyle \sum_{j=L_i}^{R_i} A_j = S_i 对于所有人 i ( 1 \le i \le M ).
约束
- 所有输入值均为整数。
- 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) 满足条件。
其总和是 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