You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

花圈装饰

题目背景

题目描述

给你一个长度为$n$的数组和$m$次操作，数组初始全为0，每次操作输入三个整数$L_i​,R_i,C_i$，你可以将$[L_i,R_i-1]$内所有数加上$C_i$，或将$[L_i,R_i-1]$外的所有数加上$C_i$，问最后数组中最大元素的最小值。注意输入的前两个数中较小者视为$L_i$，较大者视为$R_i$。

输入格式

第一行两个正整数$n$和$m$。

接下来$m$行每行一个操作，用$L_i,R_i,C_i$表示，每两个正整数之间有一个空格。

输出格式

一个正整数表示数组内最大元素的最小值。

样例 #1

样例输入 #1

5 3
1 3 1
2 4 1
3 5 2

样例输出 #1

3

提示

样例解释1：

所有操作都对区间内的数加上$C_i$，可得数组内最大元素为3。可以证明不存在其他方法使得最大元素比3更小。

数据范围

对$45\%$的数据，$n,m≤300$。

对$65\%$的数据，$n,m≤2000$。

对$85\%$的数据（包括上述的$65\%$），$C_i=1$。

对$100\%$的数据，$1≤n≤2*10^5,1≤m≤10^5,1≤C_i≤10^9$。