题目描述

题目译自 XXXII Olimpiada Informatyczna – III etap Przyjaciele i wrogowie

作为 Bajtcorp 公司的掌舵人，你肩负着管理 $n$ 名员工的重任，员工编号从 $1$ 到 $n$，每人拥有固定的工作效率 $a_i$。现在，你需要将所有员工分配到若干团队中，每个团队必须由编号连续的员工组成，其效率为团队成员效率之和。

然而，员工之间的关系错综复杂，部分员工提出了特殊要求：他们坚持与朋友同组共事，同时拒绝与不合的同事同队。若任一要求未满足，该员工的效率将降为 $0$。你收集了 $m$ 条关系约束，分为两类：

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

若某约束未满足，员工 $x_i$ 的效率将归零。需要注意的是，这些约束并非对称的，即 $x_i$ 希望与 $y_i$ 同组，并不意味着 $y_i$ 也有相同意愿。你的任务是设计一个团队分配方案，最大化所有团队效率之和。

输入格式

第一行包含两个整数 $n, m$ $(1 \leq n \leq 500000, 0 \leq m \leq 1000000)$，分别表示员工人数和约束数量。

第二行包含 $n$ 个整数 $a_i$ $(1 \leq a_i \leq 10^9)$，表示员工 $i$ 的效率。

接下来的 $m$ 行，每行包含三个整数 $t_i, x_i, y_i$ $(1 \leq t_i \leq 2, 1 \leq x_i, y_i \leq n, x_i \neq y_i)$，描述第 $i$ 条约束：$t_i = 1$ 表示员工 $x_i$ 希望与 $y_i$ 同组，$t_i = 2$ 表示员工 $x_i$ 拒绝与 $y_i$ 同组。

输出格式

输出一行，包含一个整数，表示所有团队效率之和的最大值。

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

11

最优分配为团队 $\{1, 2, 3\}$ 和 $\{4, 5\}$。员工 $5$ 的要求（与 $2$ 同组、与 $4$ 不同组）至少有一项未满足，其效率降为 $0$。其他员工的要求均满足，总效率为 $1 + 2 + 3 + 5 = 11$。

附加样例

1. $n=10, m=8$，$a_i = i$ 对于 $i=1, 2, \ldots, 10$，$t_i = [1, 1, 1, 2, 2, 2, 2, 2]$，$x_i = [2, 3, 5, 1, 4, 6, 8, 9]$，$y_i = [3, 5, 7, 4, 6, 8, 9, 10]$，答案为 $52$。
2. $n=100, m=197$，对于质数 $i$，$a_i = i$，否则 $a_i = 101 - i$；对于 $i=1, \ldots, 99$，$t_i = 1, x_i = i+1, y_i = i$，对于 $i=100, \ldots, 197$，$t_i = 2, x_i = i-99, y_i = i-97$，答案为 $3437$。
3. $n=100000, m=99999$，$a_i = (1 + (i \bmod 7))$ 对于 $i=1, \ldots, 100000$，$t_i = 2, x_i = i, y_i = i+1$ 对于 $i=1, \ldots, 99999$，答案为 $400000$。
4. $n=500000, m=0$，$a_i = 1000000$ 对于 $i=1, \ldots, 500000$，答案为 $5 \cdot 10^{11}$。

数据范围与提示

详细子任务附加限制及分值如下表所示。