题目描述

期末考完了，梦云老师决定捞捞他的学生。他决定对学生成绩进行 $q$ 次修改，每次修改需要给第$L_i$ 个学生到第 $R_i$ 个学生每人增加 $C_i$ 分。

梦云老师想知道成绩修改后全班的最低分。

输入格式

第一行输入两个整数 $n, q(1 \leq n, q \leq 10^5)$，代表学生数量和修改次数。

第二行输入 $n$ 个整数 $A_i(1 \leq A_i \leq 100)$ ，代表 $n$ 个学生的初始成绩。

接下里 $Q$ 行，每行输入三个整数 $L_i, R_i, C_i(1 \leq L_i \leq R_i \leq n, 1 \leq C_i \leq 100)$，代表每次修改。

输出格式

一个整数, 表示答案。

样例

3 2
1 1 1
1 2 1
2 3 1

2

数据范围

对于 $40\%$ 的数据，$1 \leq n, q \leq 1000$。

对于 $100\%$ 的数据，$1 \leq n, q \leq 10^5$。