Туған күнінде Карим Resident Evil ойынының жаңа бөлімін алғысы келген, бірақ оған \(n\) төбеден тұратын, \(1\)-ден \(n\)-ге дейін нөмірленген ағаш сыйлады. Әр төбеде \(a_v\) саны жазылған.

Карим бұл жағдайды пайдаланып, бір-бірімен ортақ төбесі жоқ бірнеше жолдар жиынын таңдамақ болды. \(u_1, u_2, \dots, u_k\) шыңдары арқылы өтетін жолдың құны \((a_{u_1} \oplus a_{u_2} \oplus \dots \oplus a_{u_k}) \cdot k,\) мұндағы \(\oplus\) — биттік XOR, ал \(k\) — жолдағы төбелердің саны. Жол бір төбеден тұруы мүмкін (онда оның құны \(a_v\) болады).

Таңдалған жолдардың жалпы құнын барынша арттыру қажет. Бірде бір жолды таңдамауға рұқсат етіледі (бұл жағдайда жауап \(0\)).

Енгізу

Бірінші жолда \(n\) бүтін саны беріледі (\(1 \le n \le 5000\)).
Екінші жолда \(n\) бүтін сандар жазылған \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 2000\)) төбелерде жазылған сан.
Әрбір келесі \(n-1\) жолдарында екі бүтін саннан жазылған олар \(u\) және \(v\) (\(1 \le u, v \le n\), \(u \ne v\)) — осы \(u\) және \(v\) төбелерінің арасында жол бар екенін айтады. Берілген графтың — ағаш екеніне кепілдік беріледі.

Шығару

Бір бүтін санды шығарыңыз - - - таңдалған жолдардың максималды мүмкін болатын жалпы құны.

Бағалау жүйесі

Мысалдар

Енгізу 1

5
1 2 3 4 5
1 2
2 3
2 4
1 5

Жауап 1

29

Ескертпелер

Мысал тестте жолды таңдаудың ең тиімді нұсқасы \(1!-!2!-!4\) (XOR \(= 1 \oplus 2 \oplus 4 = 7\), ұзындығы \(=3\), құны \(=7*3=21\)) және екі жеке жол — \(3\) пен \(5\) (құны \(3\) және \(5\)). Жиынтық сомасы \(=21+3+5=29\).