题目描述

大连的海滩清洁活动积分系统中，有 $n$ 位参与者，初始积分为 $a_1, a_2, ..., a_n$。进行 $p$ 次操作，每次给第 $x$ 到第 $y$ 位参与者每人增加 $z$ 分。求最终所有参与者的最低积分。

输入格式

• 第一行：两个整数 $n$ 和 $p$
• 第二行：$n$ 个整数，表示初始积分
• 接下来 $p$ 行：每行三个整数 $x$, $y$, $z$，表示增加积分的操作

输出格式

输出一个整数，表示最终所有参与者的最低积分

样例

输入样例1

3 2
1 1 1
1 2 1
2 3 1

输出样例1

2