#P17749. 火星熔岩猫的假期生活

火星熔岩猫的假期生活

题目描述

火星熔岩猫就要放假了,他想利用假期时间约妹子们出去玩-_。

他总共有 nn 天假期,其中第 ii 天他可以最多约 aia_i 个妹子出去玩。

他总共认识 mm 个妹子,其中妹子 ii 可以在 [li,ri][l_i,r_i] 天出去玩,并可以给火星熔岩猫带来 gig_i 的快乐值,但是每个妹子至多只想与火星熔岩猫出去玩一次。

对于 i<mi<m,li≤li+1l_i\le l_{i+1},ri≤ri+1r_i\le r_{i+1}。

火星熔岩猫当然知道其实他一个妹子也约不出来,但是他还是幻想自己能约出所有妹子,所以请你告诉他这个假期他最多能获得多少快乐。

输入格式

从标准输入读入。 第一行两个整数 n,mn,m。

第二行 nn 个整数表示 aia_i,表示第 ii 天最多约 aia_i 个妹子。

接下来 mm 行每行三个整数 li,ri,gil_i,r_i,g_i,妹子 ii 可以在 [li,ri][l_i,r_i] 天出去玩,并可以给火星熔岩猫带来 gig_i 的快乐值。

输出格式

输出到标准输出。 输出一个整数,表示火星熔岩猫获得的最多的快乐值。

样例输入

5 3
0 1 0 0 1
1 2 2
2 4 1
3 5 5

样例输出

7

数据范围

  • 10%:n,m≤10n,m\le10。
  • 30%:n,m≤300n,m\le300。
  • 50%:n,m≤2000n,m\le2000。
  • 70%:n,m≤5000n,m\le5000。
  • 另10%:所有 gig_i 相等。
  • 100%:n,m≤300000n,m\le300000,0≤∑ai≤m0\le\sum a_i\le m,1≤li≤ri≤n1\le l_i\le r_i\le n,1≤gi≤1091\le g_i\le10^9。