语文成绩

题目背景

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

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

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

第二行有 $n$ 个数，$a_1 \sim a_n$，代表各个学生的初始成绩。

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

输出格式

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

输入样例 #1

3 2
1 1 1
1 2 1
2 3 1

输出样例 #1

2

输入样例 #2

55 31
-2 5 52 -37 -100 -75 -100 2 -67 -35 -82 23 92 78 -79 13 -6 -20 -68 -96 -22 -94 -71 8 83 15 -47 31 -40 -47 -95 -75 -56 80 -15 83 -97 45 -82 -96 66 72 89 42 -16 21 -78 -81 55 89 60 -94 -96 -57 -61
18 46 56
43 43 5
55 55 62
37 49 2
21 35 86
37 46 86
22 43 77
55 55 83
13 22 26
1 30 58
52 52 31
19 49 51
36 44 24
20 32 35
16 31 8
36 53 21
34 47 0
51 52 19
18 55 76
37 44 77
38 48 47
33 39 75
13 26 54
52 52 2
17 17 28
24 46 27
17 24 40
54 54 55
49 49 43
21 32 42
30 53 20

输出样例 #2

-42

输入样例 #3

60 32
-63 -88 52 -45 -56 -10 26 23 50 24 27 72 4 94 -93 96 -22 36 51 -93 -4 54 -100 98 -59 -13 2 -81 -32 42 48 -12 70 67 34 -23 63 96 -53 73 94 79 87 -84 23 -81 -79 -95 24 39 10 28 1 84 -95 100 -71 32 -3 61
2 20 50
17 37 67
60 60 26
54 56 77
23 26 69
41 48 73
24 38 5
28 50 78
36 47 34
7 15 67
55 55 57
32 39 62
15 51 96
42 45 60
22 29 37
10 19 3
41 51 42
40 42 57
43 59 99
14 44 20
29 57 59
3 13 83
33 40 69
24 38 57
3 35 66
43 43 69
14 20 6
11 60 54
13 26 2
21 24 85
59 59 30
59 60 46

输出样例 #3

-63

数据范围

对于 $40\%$ 的数据，有 $n \le 10^3$。

对于 $60\%$ 的数据，有 $n \le 10^4$。

对于 $80\%$ 的数据，有 $n \le 10^5$。

对于 $100\%$ 的数据，有 $n \le 5\times 10^6$，$p \le n$，学生初始成绩 $\le 100$，$z \le 100$。