该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc404_g [ABC404G] Specified Range Sums

题目描述

给你一个整数 $N$ 和 $M$ 个整数三元组 $(L_i,R_i,S_i)$。

判断是否存在一个长度为 $N$ 的正整数数列 $A$，满足对于所有的三元组限制 $(L_i,R_i,S_i)$，满足 $\sum\limits_{j=L_i}^{R_i}A_j=S_i$。如果存在，找出合法的 $A$ 的最小元素和。

输入格式

第一行两个整数 $N,M(1\le N,M\le 4000)$。
接下来 $M$ 行，每行三个整数 $L_i,R_i,S_i(1\le L_i\le R_i\le N,1\le S_i\le 10^9)$。

输出格式

如果不存在符合条件的 $A$，输出一个整数 $-1$。
否则，输出一个整数，表示合法的 $A$ 的最小元素和。

输入输出样例 #1

输入 #1

5 3
1 2 4
2 3 5
5 5 5

输出 #1

12

输入输出样例 #2

输入 #2

1 2
1 1 1
1 1 2

输出 #2

-1

输入输出样例 #3

输入 #3

9 6
8 9 8
3 6 18
2 4 19
5 6 8
3 5 14
1 3 26

输出 #3

44

说明/提示

样例 1 解释

$A=(1,3,2,1,5)$ 是一种符合条件的情况。
此情况下 $A$ 的和是 $12$，可以证明这是可能的最小值。

样例 2 解释

此时无解。

By chenxi2009