题目描述

某校期中考试结束，学校采用一台阅卷机阅卷。老师在检查大家的成绩时，发现阅卷机阅卷有误，因此不得不手动调整大家的成绩。

现已知有 $n$ 个同学的成绩，需要做 $p$ 次调整，每次调整操作都是将第 $x$ 个同学到第 $y$ 个同学每位同学的成绩都加上 $z$ 分。

请问：经过调整后，全班同学成绩的最低分是多少分？

输入格式

第一行包含两个整数 $n$ 和 $p$，分别代表学生人数与调整次数。
第二行包含 $n$ 个整数 $a_1 \sim a_n$，代表各个学生的初始成绩。
接下来 $p$ 行，每行包含三个整数 $x, y, z$，表示给第 $x$ 个到第 $y$ 个学生每人增加 $z$ 分。

输出格式

输出一行一个整数，表示调整后全班成绩的最低分。

样例

3 2
1 1 1
1 2 1
2 3 1

2

样例解释
初始成绩为 $1, 1, 1$。
第一次调整：第 $1 \sim 2$ 个学生加 $1$，成绩变为 $2, 2, 1$。
第二次调整：第 $2 \sim 3$ 个学生加 $1$，成绩变为 $2, 3, 2$。
最终最低分为 $2$。

数据范围

• $n \le 200000$
• $p \le n$
• $1 \le x, y \le n$
• 学生初始成绩 $\le 100$
• $z \le 100$