LG#P2367. 语文成绩

语文成绩

P2367 语文成绩

题目描述

\hspace{15pt}语文考试结束了,成绩还是一如既往地有问题。

\hspace{15pt}语文老师总是写错成绩,所以当她修改成绩的时候,总是累得不行。她总是要一遍遍地给某些同学增加分数,又要注意最低分是多少。你能帮帮她吗?

输入格式

\hspace{15pt}第一行输入两个整数 $n,p \left(1 \leqq n \leqq 5 \times 10^6;\ 0 \leqq p \leqq n\right)$ 分别代表学生数量与增加分数的次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(0 \leqq a_i \leqq 100\right)$ 代表各个学生的初始成绩。

\hspace{15pt}此后 pp 行,第 ii 行输入三个整数 $x_i,y_i,z_i \left(1 \leqq x_i \leqq y_i \leqq n;\ 0 \leqq z_i \leqq 100\right)$ 代表给第 xix_i 个到第 yiy_i 个学生每人增加 ziz_i 分。

输出格式

\hspace{15pt}在一行上输出一个整数,代表更改分数后全班的最低分。

测试样例

3 2
1 1 1
1 2 1
2 3 1
2

样例 1 解释

\hspace{15pt}初始成绩为 {1,1,1}\{1,1,1\}。第一次操作给第 11 个到第 22 个学生每人增加 11 分,成绩变为 {2,2,1}\{2,2,1\};第二次操作给第 22 个到第 33 个学生每人增加 11 分,成绩变为 {2,3,2}\{2,3,2\}。因此最低分为 22。

数据范围与提示

\hspace{15pt}对于 40%40\% 的数据,n≦103n \leqq 10^3;

\hspace{15pt}对于 60%60\% 的数据,n≦104n \leqq 10^4;

\hspace{15pt}对于 80%80\% 的数据,n≦105n \leqq 10^5。