← 返回题目列表

AtCoder · abc404_g

G. 指定范围总和

中文机器翻译题面 查看原题

分数: 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