题目描述:

如题.这是一道题面和思维以及代码实现都很中等的题.

你现在有 $n$ 个数字,注意这 $n$ 个数字是不给定的.然后你有 $k$ 个区间 $[a_l,a_r]$.你可以选择一个区间,花费 $w[i]$,然后将区间 $[a_l,a_r]$ 内的所有数字同时增加或减少同一个值 $g$ (注意这个 $g$ 是可以任意选取的).

现在你的任务是求一个方案,这个方案满足无论 $n$ 个数字分别是多少,都能将所有的数字变为 $0$,如果存在多个方案,输出花费最小的方案的花费.假设没有合法的方案,则输出 $-1$

就比如 $3$ 个数字分别为 $1,2,1$,并且有 $1$ 个区间 $[1,2]$,那么你可以将区间 $[1,2]$ 的所有数字增减任意值,比如同时变为 $[0,1]$ 或者 $[3,4]$. 并且需要注意的是 $n$ 个值是不给定的,例如,当三个数字为 $1,1,1$ 的时候,你只选择区间 $[1,3]$ 就是合法的,但是这三个数字可以为$1,2,3$,此时你的选择方案就是不合法的了.

输入格式:

第一行输入两个正整数 $n,k$,表示一共有 $n$ 个数,以及有 $k$ 个可修改区间

接下来 $k$ 行,每行三个数,表示区间的左右端点 $l,r$,以及需要花费的 $w$

输出格式:

输出合法方案的最小总花费,若没有合法的方案,则输出-1

输入输出样例:

输入#1

5 6
1 2 3
1 3 4
2 4 5
4 5 1
2 3 2
3 5 6

输出#1

15

数据范围:

对于$100\%$的测试点保证$n\in[1,2e5],k\in[1,1e6]$,$l_i,r_i\in[1,min(1e5,n)]$,$w_i\in[1,1e9]$