C. КПП
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В вашем городе n перекрестков. Между этими перекрестками расположены m односторонних дорог. Вы — мэр города, и вы должны обеспечивать безопасность на всех перекрестках.

Для обеспечения безопасности перекрестков нужно построить пункты КПП. КПП можно построить только на перекрестке. КПП на перекрестке i может обезопасить перекресток j, либо если i = j, либо если полицейская машина может доехать до j от i и затем вернуться в i.

Постройка КПП стоит денег. Так как некоторые районы города дороже других, то на некоторых перекрестках строить КПП дороже, чем на других. Какую минимальную сумму денег необходимо потратить для обеспечения безопасности всех перекрестков? Сколько существует оптимальных способов постройки КПП (в дополнение к минимальной стоимости подстройки, вы должны построить как можно меньше КПП)? Два способа считаются различными, если в одном из них некоторый перекресток имеет КПП, а в другом — нет.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество перекрестков. В следующей строке записано через пробел n целых чисел: i-е число равняется цене постройки КПП на i-м перекрестке (цена неотрицательная и не превышает 109).

В следующей строке записано целое число m (0 ≤ m ≤ 3·105) — количество дорог. В каждой из следующих m строк записано по два целых числа, ui и vi (1 ≤ ui, vi ≤ n; u ≠ v). Пара ui, vi означает, что в городе есть дорога, ведущая из перекрестка ui в перекресток vi. Гарантируется, что во входных данных между двумя перекрестками не может быть более одной дороги в одном направлении.

Считайте, что все перекрестки пронумерованы целыми числами от 1 до n.

Выходные данные

Выведите два целых числа через пробел. Первое число — минимально возможная сумма денег, необходимая для того, чтобы обеспечить безопасность всех перекрестков. Второе число — количество способов обеспечения безопасности. Так как количество способов может быть достаточно большим, выведите его по модулю 1000000007 (109 + 7).

Примеры
Входные данные
3
1 2 3
3
1 2
2 3
3 2
Выходные данные
3 1
Входные данные
5
2 8 0 6 0
6
1 4
1 3
2 4
3 4
4 5
5 1
Выходные данные
8 2
Входные данные
10
1 3 2 2 1 3 1 4 10 10
12
1 2
2 3
3 1
3 4
4 5
5 6
5 7
6 4
7 3
8 9
9 10
10 9
Выходные данные
15 6
Входные данные
2
7 91
2
1 2
2 1
Выходные данные
7 1