#2475. csp初赛成绩

csp初赛成绩

题目描述

CCF的特派员总是写错成绩,所以当她修改成绩的时候,总是累得不行。她总是要一遍遍地给某些同学增加分数,又要注意最低分是多少。你能帮帮她吗?

输入格式

第一行有两个整数 nnpp,代表学生数与增加分数的次数。

第二行有 nn 个数,a1ana_1 \sim a_n,代表各个学生的初始成绩。

接下来 pp 行,每行有三个数,xxyyzz,代表给第 xx 个到第 yy 个学生每人增加 zz 分。

输出格式

输出仅一行,代表更改分数后,全班的最低分。

样例 #1

样例输入 #1

3 2
1 1 1
1 2 1
2 3 1

样例输出 #1

2

提示

对于 40%40\% 的数据,有 n103n \le 10^3

对于 60%60\% 的数据,有 n104n \le 10^4

对于 80%80\% 的数据,有 n105n \le 10^5

对于 100%100\% 的数据,有 n5×106n \le 5\times 10^6pnp \le n,学生初始成绩 100 \le 100z100z \le 100