该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

2025 年花都区学生数字素养提升实践大赛活动

创意趣味算法项目中学组试题

（时间：2025 年 5 月 29 日下午 14:30-16:30，4 大题共 400 分，每题 100 分。各题默认 运行最大时间 1 秒，占用最大内存 128MB，采用标准输入输出模式，代码文件名保存为 题目序号.cpp，如 1.cpp，保存在以座位号+姓名命名的文件夹里，然后提交。）

题目描述

数学考完了，又到了数学老师难办的时候。数学老师想捞同学一把，她总是要一遍遍地给某些同学增加分数（均为正整数），又要注意最低分是多少。由于工作量很大，你能帮帮她吗？

输入格式

第一行有两个整数 n，p，代表学生数与增加分数的次数；

第二行有 n 个数，a[1]～a[n],代表各个学生的初始成绩；

接下来 p 行，每行有三个数 x，y，z，代表给第 x 个到第 y 个学生每人增加 z分。

输出格式

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

样例

3 2
1 1 1
1 2 1
2 3 1

2

备注

n≤100000,p≤n ,学生初始成绩≤100，z≤100。

1-10测试点为官方测试数据

11-20测试点为BCOI补充测试数据

对于11-14的数据，有 $n\le{10}^3；$

对于15-16的数据，有 $n\le{10}^4；$

对于17-18的数据，有 $n\le{10}^5；$

对于19-20的数据，有 $n\le{10}^6；$