TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7630
  • 题目
  • P7630修改
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    果老师有一个长度为 \(n\) 的数列

    一个不幸的事实是,这个数列里的数非常地混乱,果老师想让它变得工整

    果老师现在有 \(m\) 种操作,第 \(i\) 种操作可以把 \([l_i, r_i]\) 之间的数全部加一或减一,但是,要使用它就必须先支付 \(w_i\) 的费用,然后就可以无限制次数地使用这种操作

    果老师想要知道,对于任意长度为 \(n\) 的数列,是否存在一种选择操作的方式,可以通过使用这些操作,使得所有数列中的数都等于 $0$

    果老师并不富有,因此如果有解,他还想要知道最少支付多少费用

    输入格式

    第一行两个整数 \(n,m\) ,表示数列长度和操作个数

    接下来 \(m\) 行,每行三个整数 \(l_i,r_i,w_i\),意义见题目描述

    \(n\le 10^5,m\le 2\times 10^5\)

    \(1\le l_i\le r_i\le n,1\le w_i\le 10^9\)

    输出格式

    如果不存在一种选择操作的方式,输出 \(-1\)

    否则输出最少支付的费用

    样例输入 1

    2 3
    1 2 3
    1 1 100
    2 2 101

    样例输出 1

    103

    样例输入 2

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

    样例输出 2

    -1