题目描述

强哥最近在玩一款勇者斗恶龙的大型RPG游戏，在该游戏中，玩家可以培养多个角色。每个角色初始都有一个战斗力数值。游戏会定期举办"训练营"活动，玩家可以选择一批连续的角色进行集中训练，提升他们的战斗力。

活动结束后，需要找出当前所有角色中的最低战斗值。你能帮帮强哥吗？

输入格式

第一行有两个整数 $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

2

说明/提示

对于 $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 1000$，$z \le 1000$。