Sumo and Electricity(Hard)
题号：NC207578
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

注意：Easy与Hard版本的不同之处在于w_i的条件限制，Hard中存在多个 w_i 满足 。

Sumo有n个核电站，每个核电站都有自己的耗电量。这些核电站之间通过m条电缆相连，电缆的传输功耗为两个核电站耗电量之间的异或（XOR）值。

但是核电站功率十分不稳定，因此Sumo并不知道部分核电站目前的功耗是怎样的，但是它可以选择调整这些核电站功耗的大小。

因为电缆的功耗远大于核电站的功耗，因此Sumo希望可以优先保证在所有电缆功耗总和尽可能低的条件下，尽量降低所有核电站的功耗总和，希望你能帮助Sumo为功耗未知的核电站设置功耗，从而满足以上的条件。

输入描述:

第一行输入整数  代表有n个核电站，m条电缆。

接下来的一行中给出n个整数代表第i个核电站的功耗， 代表这个核电站的功耗未知。

接下来 m 行，每行输入两个数 表示该条电缆所连接的两个核电站的编号，数据保证两个核电站之间不会有多条电缆连接。

输出描述:

第一行输出一个整数表示电缆功耗总和。

第二行输出一个整数表示在电缆功耗总和尽可能低的情况下，核电站的功耗总和。
示例1

输入

复制 
4 4
1 -1 -1 10
1 3
1 2
2 3
2 4

输出

复制 
11
13

备注:

样例中当Sumo将2,3两个核电站的功耗设置为1,1时，电缆总功耗为：+++=11，总功耗最小，核电站的功耗总和为13。