에스컬레이터

Binary Casino는 N개의 층으로 이루어진 특별한 초고층 빌딩으로, 고속 에스컬레이터가 복잡한 네트워크로 층들을 연결한다.

층 연결 구조는 다음과 같다. 층 A에서 층 B로 가는 에스컬레이터가 있으면, 층 B에서 층 A로 가는 에스컬레이터도 있다. 또한 임의의 두 층 A와 B에 대해 A에서 B로 가는 방법은 정확히 하나뿐이다.

관리자는 더 많은 고객을 유치하려고 프로모션 게임을 열기로 했다. 게임 규칙은 다음과 같다.

• 게임은 한 라운드 이상으로 진행된다.
• 각 라운드에서 고객은 라운드를 시작할 층 S를 고를 수 있다. 이때 층 S에 연관된 고정 토큰 수 t(S)를 얻는다. 그런 다음 에스컬레이터를 이용해 다른 층으로 이동할 수 있다.
• 고객이 층 A에서 층 B로 에스컬레이터를 타기로 하고 X개의 토큰을 가지고 있으면, 층 B에 들어가기 위해 X − (X AND t(B))개의 토큰을 내야 한다. 여기서 "AND"는 비트 AND 연산자, "−"는 수에 대한 표준 뺄셈 연산자이며, t(B)는 층 B에 연관된 토큰 수이다.
• 고객은 어느 층에서든(S 포함) 라운드를 멈추고 그 라운드의 토큰을 가질 수 있다. 그런 다음 가능하다면 어느 층에서든 새 라운드를 시작할 수 있다.
• 두 라운드는 시작 층과 끝 층의 쌍이 같을 수 없다. 시작 층과 끝 층을 맞바꾼 경우도 마찬가지이다.

관리자는 고객이 게임에서 얻을 수 있는 최대 토큰 수가 궁금하다.

입력의 첫 줄에는 카지노 초고층 빌딩의 층 수를 나타내는 정수 N (1 ≤ N ≤ 3 · 10^5)이 주어진다. 둘째 줄에는 N개의 정수 Vi (0 ≤ Vi < 2^20)가 주어진다. i번째 정수 Vi는 고객이 i번째 층에서 얻는 토큰 수를 나타낸다. 그다음 N − 1개의 줄이 주어진다. 각 줄에는 에스컬레이터로 연결된 두 층 A와 B (0 ≤ A, B < N)를 나타내는 두 정수가 주어진다.

고객이 얻을 수 있는 최대 토큰 수를 하나의 수로 출력한다.