说明

CLX 发明出了超级氢弹，于是，一场战争在 CLX 和 ZCX 之间打响了...

ZCX 的军队装备十分落后，连一枚氢弹都没有，于是 ZCX 只好采取人头战术，于是，全世界范围内的征兵开始了。

经过第一次选拔，有 $n$ 个人脱颖而出，每一个人都有一个较高的战斗值。ZCX 要求在最后选出来的人中任何两个人都必须是没有一点关系的（包括亲戚关系），这样才能保证在战场上每位战士都能心无杂念地奋勇杀敌。可恰恰不幸的是，在这 $n$ 个人当中，有某一些人具有一些很遥远的亲戚关系，比如 A 的父亲的父亲的父亲的父亲（……）与 B 的母亲的母亲的母亲的母亲（……）是夫妻，那么就说 A 与 B 有亲戚关系。而现在 ZCX 急想在 $1s$ 的时间内知道这 $n$ 个人能组成多大的军队以及在保证人数最大的情况下的军队的最大战斗力（指军队中每个战士的战斗值之和）是多少，所以就把这个任务叫给了统计部部长的你来解决。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个战士的战斗值；

接下来若干行（行数 $\le n$），每行两个数 $A_i$ 和 $B_i$，表示 $A_i$ 和 $B_i$ 两位战士具有微妙的亲戚关系。

输入数据保证不出现 $A_i = B_i$ 的情况，但一种情况多次出现是允许的，谁叫他们两太亲呢！

注：保证输入数据和答案都在 long int 范围内。

输出格式

输出共两行，第一行为最大军队人数，第二行为军队的最大战斗力。

样例

10
291 2306 668 2710 1524 1318 602 2991 2881 2951
4 6
9 4
4 7
9 1
10 1
7 10
1 9

5
10440

提示

对于 $30 \%$ 的数据 $1\le n \le 10$；

对于 $100 \%$ 的数据 $1\le n \le 300000$。