Ilya 热衷于约会！他正在为接下来的 $t$ 天（这些天编号为 $1$ 到 $t$）规划约会。对于每一天 $x$，他知道自己最多能安排 $a_x$ 次约会。

Ilya 认识 $n$ 位女孩，编号为 $1$ 到 $n$。第 $i$ 位女孩愿意在 $[l_i, r_i]$ 范围内的任意一天与他约会，且每位女孩最多只能与他约会一次。与第 $i$ 位女孩约会，Ilya 可以获得 $p_i$ 的愉悦值。对于所有 $i < n$，满足 $l_i \le l_{i+1}$ 且 $r_i \le r_{i+1}$。

Ilya 的目标是选择一些女孩并安排约会日期，以使总愉悦值最大化。请帮帮他！计算他通过合理选择女孩和约会日期所能获得的最大总愉悦值。

输入格式

第一行包含两个整数 $n$ 和 $t$：女孩的数量和天数（$1 \le n, t \le 300\,000$）。

第二行包含 $t$ 个整数 $a_1, a_2, \dots, a_t$：其中 $a_i$ 表示 Ilya 在第 $i$ 天最多能安排的约会次数（$0 \le a_i \le n$）。

接下来的 $n$ 行包含女孩的描述。第 $i$ 行包含三个整数 $l_i, r_i$ 和 $p_i$：表示第 $i$ 位女孩约会日期区间的边界以及 Ilya 与她约会能获得的愉悦值（$1 \le l_i \le r_i \le t$，$1 \le p_i \le 10^9$）。

保证对于每个 $i < n$，满足 $l_i \le l_{i+1}$ 且 $r_i \le r_{i+1}$。

输出格式

输出一个整数：Ilya 通过合理选择女孩和约会日期所能获得的最大总愉悦值。

样例

样例输入 1

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

样例输出 1

7