#P2811. Protect the school

Protect the school

题目背景

话说上回保安因为奶牛事件而搞得地位岌岌可危,所以他们决定好好看守这个学校,他们有一个计划。但是由于学校太大了,他们计划不好,所以找到上次帮他的你,请你解决他的苦难。然后他又可以开始了手机游戏之旅。

题目描述

学校有 nn 个检查点,由于保安懒得动脑筋,他们决定在这 nn 个检查点之间建立 mm 条通道,由于学校的懒政以及军事化管理,这些路是单向的,逆向通过会被处分。保安们人手不够(游戏任务太多),他们决定只挑选一些点来站岗,由于保安身怀绝技,可以瞬间通过任何他站岗点可以走到的路(瞬移到到任何连通的点)。每一个检查点有一个值表示这个点的困难程度。为了保护学校,请你帮他们出个主意,保证一旦有一个检查点发生事件,都能有保安瞬间抵达。但是为了舒服和管理便利,请你告诉他们在使用最少的保安数量的情况下最小的困难总和。

输入格式

第一行一个整数 nn,代表检查点数量。

接下来一行 nn 个整数,代表困难程度。

接下来一行一个数 mm,表示道路的数量。

接下来 mm 行每行两个整数 u,vu,v 代表 uuvv 有一条单向通道。

输出格式

两个整数。

第一个整数表示最小困难和。第二个整数表示在保证最小困难和以及最少保安数量的条件下,可选的方案总数。

5
31619 26195 18669 1198 178
4
2 4
3 5
1 2
4 1
20045 1

提示

1n104,1m5×1041 \le n \le 10 ^ 4,1 \le m \le 5 \times 10 ^ 4,保证答案在 int 范围内。