#2644. 语文成绩

语文成绩

题目背景

语文考试结束了,成绩还是一如既往地有问题。

题目描述

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

输入格式

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

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

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

输出格式

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

样例

3 2
1 1 1
1 2 1
2 3 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