题目描述

有 $n$ 个物品，第 $i$ 个物品的价值为 $a_i$。

有 $m$ 条限制条件，第 $i$ 条限制条件描述为 $x_i, y_i$，表示选择第 $x_i$ 个物品后就不能再选择第 $y_i$ 个物品，反之亦然（即 $x_i$ 和 $y_i$ 不能被同时选择）。此时我们说这两个物品互相排斥。

保证所有限制条件之间不存在矛盾或循环，且不存在一种无法满足限制条件的物品选择方案 $p_1, p_2, \dots, p_k$，使得 $p_1$ 排斥 $p_2$，$p_2$ 排斥 $p_3$，……，$p_{k - 1}$ 排斥 $p_k$，$p_k$ 排斥 $p_1$。

求能选到的最大价值，以及价值最大的前提下最少选几件物品。

可以证明，在上面的约束条件下，一定有解。

输入格式

第 $1$ 行两个非负整数 $n, m$。

第 $2$ 行 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。

接下来 $m$ 行，每行两个正整数 $x_i, y_i$。

输出格式

一行，两个非负整数，表示最大价值和最少选择的物品件数。

1 0
2

2 1

5 2
2 8 6 9 8
1 2
2 3

25 3

说明/提示

【数据范围】

对于 $100\%$ 的测试数据，$1 \le m \lt n \le 5 \times 10^5$，$1 \le x_i, y_i \le n$，$x_i \neq y_i$，$0 \le a_i \le 3.6 \times 10^{12}$。

保证答案不超过 $64$ 位无符号整数范围。

【特殊限制】

本题使用捆绑测试。

Subtask #1（5 分）：$a_i = 0$。

Subtask #2（5 分）：$n \le 20$。

Subtask #3（10 分）：$m \le 10$。

Subtask #4（10 分）：$m \le 1000$。

Subtask #5（10 分）：$n \le 10^5$。

Subtask #6（10 分）：$x_i + 1 = y_i$。

Subtask #7（50 分）：无特殊限制。