Migrated from Lutece 2857 幸运之石

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

商人晶歌为了某件事相当烦恼。
『纳因瓦利・帝都分店』开张使她打入了帝都市场，进一步扩展了营业版图。然而，要更进一步发展，需要配得上业务需求的「代步工具」。
为了生意，她需要「代步工具」，然而，光靠自己的零用钱是不够的。
正当她心情低落地继续工作时，某一天，正在接受猎犬训练的爱犬克鲁贝洛斯不知从哪里捡回了一颗奇特的石头。
「真是颗怪石头啊──」
晶歌将这颗奇特的石头拿在手上。从那一天起，不知为何，各式各样的人开始造访『纳因瓦利』。

这颗奇特的石头上有 $n$ 个镶嵌槽，每个镶嵌槽中可以镶嵌一定数量的耀晶片。具体来说，第 $i$ 个镶嵌槽最多只能镶嵌 $a_i$ 个耀晶片。

要使这块奇特的石头发挥它神奇的功效，要满足 $m$ 个限制。具体来说，对于第 $i$ 个限制，要满足第 $l_i,l_i+1,\ldots,r_i$ 个镶嵌槽的总耀晶片的个数和大于或等于 $w_i$。

现在晶歌想知道，最少需要多少个耀晶片才能使得石头开始工作。

镶嵌槽从 $1$ 开始编号。

Input

输入第一行，包含两个整数 $n,m\ (1\le n,m\le 10^5)$。

第二行有 $n$ 个整数 $a_i\ (1\le a_i\le 5\times 10^3)$。

第 $3\sim m+2$ 行，每行三个整数 $l_i,r_i,w_i\ (1\le l_i\le r_i\le n,0\le w_i\le 10^9)$。

Output

输出一个整数表示最少需要的耀晶片数量，数据保证至少存在一组解。

Samples

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

8

Resources

The 19th UESTC Programming Contest Preliminary