题目描述

语文老师在黑板上写了 $n$ 个同学的成绩 $a_1,a_2,\dots,a_n$。接下来进行了 $p$ 次操作，每次操作把下标在 $[x,y]$ 内的所有同学的成绩同时加上 $z$（$z$ 可能为负数）。

所有操作结束后，请输出所有同学成绩中的最小值。

输入格式

第一行两个整数 $n,p$。 第二行 $n$ 个整数，表示初始成绩。 接下来 $p$ 行，每行三个整数 $x,y,z$。

输出格式

一个整数，操作后成绩的最小值。

样例输入 #1

3 2
1 1 1
1 2 1
2 3 -3

样例输出 #1

0

数据范围

$1\le n,p\le 5\times10^6$，$-500\le a_i,z\le 500$，$1\le x\le y\le n$。