作为 Bajtcorp 公司的负责人，你需要管理 $n$ 名员工，编号从 $1$ 到 $n$。你已经确定了每名员工 $i$ 的效率为 $a_i$。现在，你想将所有员工划分为若干个团队。每个团队必须由编号构成连续区间的员工组成，团队的效率为其成员的效率之和。

遗憾的是，一些员工对团队有特殊要求：他们坚持与自己的朋友在同一个团队工作，并拒绝与他们讨厌的人在同一个团队工作。如果一名员工的任何一个要求没有得到满足，他的效率就会降为 $0$。你收集了 $m$ 条关于这些要求的信息，每条信息属于以下两种类型之一：

1. 员工 $x_i$ 希望与员工 $y_i$ 在同一个团队。
2. 员工 $x_i$ 不希望与员工 $y_i$ 在同一个团队。

未能满足此类要求会导致员工 $x_i$ 的效率降为 $0$。请注意，如果员工 $x_i$ 希望与员工 $y_i$ 在同一个团队，并不一定意味着员工 $y_i$ 也希望与员工 $x_i$ 在同一个团队。换句话说，收集到的要求不一定是对称的。

你的任务是找到一种团队划分方式，使得所有团队的效率之和最大化。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 500\,000, 0 \le m \le 1\,000\,000$)，分别表示员工数量和要求数量。 下一行包含 $n$ 个整数，其中第 $i$ 个数为 $a_i$ ($1 \le a_i \le 10^9$)，表示员工 $i$ 的效率。 接下来的 $m$ 行包含有关后续要求的信息。第 $i$ 行包含三个整数 $t_i, x_i, y_i$ ($1 \le t_i \le 2, 1 \le x_i, y_i \le n, x_i \neq y_i$)，表示关于员工 $x_i$ 和 $y_i$ 的类型为 $t_i$ 的信息，其中 $t_i = 1$ 表示类型 1（即员工 $x_i$ 希望与员工 $y_i$ 在同一个团队），$t_i = 2$ 表示类型 2（即员工 $x_i$ 不希望与员工 $y_i$ 在同一个团队）。

输出格式

你的程序应输出一行，包含所有团队效率之和的最大值。

样例

样例输入 1

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

样例输出 1

11

说明 1

最优划分为 $\{1, 2, 3\}, \{4, 5\}$。此时员工 $5$ 的至少一个要求未得到满足，因此他的效率降为 $0$。所有其他员工的要求均得到满足，因此所有团队的效率之和为 $1 + 2 + 3 + 5 = 11$。

子任务

测试集分为以下子任务。每个子任务的测试用例由一个或多个独立的测试组组成。