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

题目描述

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

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

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

输入格式

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

输出格式

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

样例输入

3 2
1 1 1
1 2 1
2 3 1

样例输出

2

样例解释

初始时3个学生的成绩分别为1、1、1。 第一次调整操作是给第1个到第2个学生每人加1分，调整后成绩变为2、2、1。 第二次调整操作是给第2个到第3个学生每人加1分，调整后成绩变为2、3、2。 此时全班学生的成绩为2、3、2，其中的最低分是2。

数据范围

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