问题描述

塔子哥有一项特殊技能，可以降低连绵山峰的高度。每次施法，他能够选定一段连续的山峰区域，使得这些山峰的高度均匀降低。现在他想知道，通过有限次施法之后，何时能使得至少有一个山峰的高度降至海平面以下（高度小于等于 0）。已知山峰的数量和施法的次数，请计算出何时可以实现目标。

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别表示山峰的数量和施法的次数。

第二行包含 $n$ 个正整数 $H_1, H_2, ..., H_n$，表示每个山峰的初始高度。

接下来的 $m$ 行，每行包含三个正整数 $L_i, R_i, h_i$，表示每次施法作用的山峰区间 $[L_i, R_i]$ 和降低的高度 $h_i$。

输出格式

输出一个整数，表示在第几次施法之后，至少有一个山峰的高度降至海平面以下。

样例输入

5 4
6 5 3 4 6
1 3 2
4 4 2
3 5 1
1 5 6

样例输出

3

评测数据与规模

• 对于 $1 \le n, m \le 10^5$，$1 \le h_i, H_i \le 10^9$，$1 \le L_i \le R_i \le n$ 的输入数据，保证有解。