Maximum Sum of Non-Adjacent Cities

You are given an undirected graph representing a network of n cities. Each city i has an associated importance value a_i. There are n-1 roads connecting these cities such that each road represents a direct connection between two cities. Two cities are considered adjacent (directly connected) if there is a road between them.

Your task is to select a pair of distinct cities i and j (i < j) such that they are not directly connected and the sum of their importance values, i.e., a_i + a_j, is maximized. In mathematical notation, you need to find:

$$\max_{1 \le i < j \le n,\; i \not\sim j} \left\{ a_i + a_j \right\} $$

If no valid pair of cities exists (i.e. every possible pair is directly connected), output 0.

Note: The input consists of multiple datasets. Each dataset is separated by a line containing a single 0.

inputFormat

The input contains multiple datasets. For each dataset:

• The first line contains a single integer n (n ≥ 2), representing the number of cities.
• The second line contains n space-separated integers representing the importance values a1, a2, ..., an.
• The next n - 1 lines each contain two integers u and v indicating there is a road connecting city u and city v.
• A line containing a single 0 follows each dataset to mark its end.

The entire input is read from stdin.

outputFormat

For each dataset, output a single line containing one integer: the maximum sum of importance values of any two non-adjacent cities. If no such pair exists, output 0. The output should be written to stdout.

## sample

4
1 2 3 4
1 2
1 3
1 4
0

7

</p>