Paimon’s Crystalfly Catching

Paimon is catching crystalflies on a tree – a connected graph with \(n\) vertices and \(n-1\) edges. The \(i\)-th vertex initially has \(a_i\) crystalflies. When Paimon arrives at a vertex, she immediately catches all the crystalflies there. However, the crystalflies are timid. When Paimon reaches a vertex, all crystalflies on every adjacent vertex get disturbed. Specifically, if the crystalflies on vertex \(i\) are disturbed for the first time at the beginning of the \(t'\)-th second, then they will disappear at the end of the \(t' + t_i\)-th second.

At the beginning of the 0-th second, Paimon is at vertex 1 and catches the crystalflies there. (Assume that the crystalflies on vertex 1 will never vanish.) Immediately upon her arrival, every neighbor of vertex 1 is disturbed; thus, for any vertex \(i\) adjacent to 1 the crystalflies will vanish at the end of \(0 + t_i\)-th second if not caught in time.

After that, at the beginning of every subsequent second, she can perform one of the following operations:

• Move to an adjacent vertex. (If the destination vertex’s crystalflies are scheduled to disappear at the end of that same second, she can still catch them upon arrival.)
• Stay in her current vertex (although delaying is never beneficial).

Note that whenever Paimon reaches a vertex (even if the crystalflies there have already disappeared), the moment of her arrival will disturb all adjacent vertices (if they have not yet been reached). In other words, for any vertex \(i\) (other than vertex 1) whose adjacent vertex \(j\) is visited at time \(T\), we say that vertex \(i\) is disturbed at time \(T\), and its crystalflies vanish at the end of the \(T + t_i\)-th second if Paimon has not visited \(i\) by then.

Given that Paimon has an astronomically long time \(10^{10^{10^{10^{10}}}}\) seconds to move, determine the maximum total number of crystalflies she can catch if she chooses her route optimally.

Input/Output note: Although the time is huge, the optimal strategy is constrained by the deadlines induced by the disturbance – once a vertex is disturbed (by any neighbor reached) its clock starts, so any detour that delays reaching a vertex might cause it to vanish before arrival.

It is guaranteed that \(n\) is relatively small (for example, \(n \le 6\)), so that an exponential‐time solution (e.g. brute force DFS over all feasible routes) can pass.

inputFormat

The input consists of the following:

1. An integer \(n\) indicating the number of vertices.
2. A line containing \(n\) integers: \(a_1, a_2, \dots, a_n\), where \(a_i\) denotes the number of crystalflies initially at vertex \(i\).
3. A line containing \(n\) integers: \(t_1, t_2, \dots, t_n\), where \(t_i\) is the time delay after disturbance before the crystalflies at vertex \(i\) vanish.
4. \(n-1\) lines follow, each containing two integers \(u\) and \(v\) (1-indexed), representing an undirected edge.

Note: Vertex 1 is where Paimon starts at time 0.

outputFormat

Output a single integer – the maximum number of crystalflies Paimon can catch if she follows an optimal route.

sample

3
5 10 20
100 1 2
1 2
2 3

35