*【差分约束】[ABC404G] Specified Range Sums
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
AT_abc404_g [ABC404G] Specified Range Sums
题目描述
给你一个整数 和 个整数三元组 。
判断是否存在一个长度为 的正整数数列 ，满足对于所有的三元组限制 ，满足 。如果存在，找出合法的 的最小元素和。
输入格式
第一行两个整数 。
接下来 行，每行三个整数 。
输出格式
如果不存在符合条件的 ，输出一个整数 。
否则，输出一个整数，表示合法的 的最小元素和。
输入输出样例 #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 解释
是一种符合条件的情况。
此情况下 的和是 ，可以证明这是可能的最小值。
样例 2 解释
此时无解。
By chenxi2009