Protect the school
题目背景
话说上回保安因为奶牛事件而搞得地位岌岌可危,所以他们决定好好看守这个学校,他们有一个计划。但是由于学校太大了,他们计划不好,所以找到上次帮他的你,请你解决他的苦难。然后他又可以开始了手机游戏之旅。
题目描述
学校有 $n$ 个检查点,由于保安懒得动脑筋,他们决定在这 $n$ 个检查点之间建立 $m$ 条通道,由于学校的懒政以及军事化管理,这些路是单向的,逆向通过会被处分。保安们人手不够(游戏任务太多),他们决定只挑选一些点来站岗,由于保安身怀绝技,可以瞬间通过任何他站岗点可以走到的路(瞬移到到任何连通的点)。每一个检查点有一个值表示这个点的困难程度。为了保护学校,请你帮他们出个主意,保证一旦有一个检查点发生事件,都能有保安瞬间抵达。但是为了舒服和管理便利,请你告诉他们在使用最少的保安数量的情况下最小的困难总和。
输入输出格式
输入格式
第一行一个整数 $n$,代表检查点数量。
接下来一行 $n$ 个整数,代表困难程度。
接下来一行一个数 $m$,表示道路的数量。
接下来 $m$ 行每行两个整数 $u,v$ 代表 $u$ 到 $v$ 有一条单向通道。
输出格式
两个整数。
第一个整数表示最小困难和。第二个整数表示在保证最小困难和以及最少保安数量的条件下,可选的方案总数。
输入输出样例
输入样例 #1
5
31619 26195 18669 1198 178
4
2 4
3 5
1 2
4 1
输出样例 #1
20045 1
说明
$1 \le n \le 10 ^ 4,1 \le m \le 5 \times 10 ^ 4$,保证答案在 `int` 范围内。