题目描述

成绩复核结束后，老师需要对若干连续编号的同学统一调整分数。每次操作会把第 $x$ 名到第 $y$ 名同学的成绩都增加 $z$ 分，$z$ 也可能是负数。

所有调整完成后，老师只需要知道全班最低分是多少。请你帮助完成统计。

输入格式

第一行包含两个整数 $n,p$，分别表示学生人数和调整次数。

第二行输入 $n$ 个整数，表示初始成绩。

接下来 $p$ 行，每行输入三个整数 $x,y,z$，表示给编号在 $[x,y]$ 内的同学统一增加 $z$ 分。

输出格式

输出所有调整完成后的最低分。

5 3
70 80 90 60 75
1 3 5
4 5 10
2 4 -3

67

数据范围与提示

• $1\le n,p\le 2\times10^5$
• 初始成绩和调整值的绝对值均不超过 $10^9$