Ant and Bob two army want to capture a country. The country is consist of N cities. To capture the city i, it takes Ant A[i] minutes, and Bob needs B[i] minutes to capture city i. Due to the similarity of neighboring cities, If the city i and j are neighboring cities, if Ant has captured city i, then the time for Ant to capture city j is A[j]/2. Of course if Ant has captured city j, then the time for Ant to capture city i is A[i]/2. It is the same for Bob. We define the total time to capture a country be the time to capture city 1 + the time to capture city 2 + ... + the time to capture city N. Now we want to know the minimal total time. For simplicity, we assume that there is only one path to go from one city to another city.
输入解释
The first line contains a integer N(0<N<100), which is the number of cities.Then following N lines describe A[1], A[2], …, A[N];Then following N lines describe B[1], B[2], …, B[N];Next comes N-1 lines, each contains two integers x, y, meaning that city x and city y are neighboring.
输出解释
Just output the minimal total time in a single line.