语文成绩

题目背景

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

题目描述

语文老师总是写错成绩,所以当她修改成绩的时候,总是累得不行。她总是要一遍遍地给某些同学增加分数,又要注意最低分是多少。你能帮帮她吗? //这又跟神器有什么关系呢?神说:呵呵。 //因为n和p的范围比较大 建议C++选手使用scanf读入. //同时建议写读入优化.... //最后一个点,亲测pas读入800+ms,c/C++的scanf 1200+ms,所以这个点的时限改为2s

输入输出格式

输入格式


第一行有两个整数n,p,代表学生数与增加分数的次数。 第二行有n个数,a1~an,代表各个学生的初始成绩。 接下来p行,每行有三个数,x,y,z,代表给第x个到第y个学生每人增加z分。

输出格式


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

输入输出样例

输入样例 #1

3 2
1 1 1
1 2 1
2 3 1

输出样例 #1

2

说明

对于40%的数据,有n<=1000 对于60%的数据,有n<=10000 对于80%的数据,有n<=100000 对于100%的数据,有n<=5000000,p<=n,学生初始成绩<=100,z<=100