Birthday Gift

Xiaomiao's birthday is approaching, and to prepare a gift for her, Xiaocong visits a shopping street consisting of \(n\) shops. The shops are connected by roads that form a tree.

Each shop \(i\) sells a unique item. The item from shop \(i\) has a price of \(c_i\), an available stock of \(d_i\), and gives a happiness (or affection) value of \(w_i\) per unit bought. However, the shops have a strange rule: if you purchase something in shops \(u\) and \(v\) and there is any shop \(p\) on the unique simple path between \(u\) and \(v\), then you must also make a purchase at shop \(p\). In other words, the set of shops where you make a purchase must form a connected subtree of the shopping street.

With a total budget of \(m\) units of money, Xiaocong wants to maximize the total happiness by choosing a connected set of shops and deciding how many items to buy at each shop (at least one item per chosen shop, but no more than the available stock). The goal is to maximize the sum \[ \sum_{i \in S} x_i \cdot w_i, \] subject to \[ \sum_{i \in S} x_i \cdot c_i \le m, \quad 1 \le x_i \le d_i, \quad S \text{ is connected}. \]

Input: The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\). The third line contains \(n\) integers \(c_1, c_2, \dots, c_n\). The fourth line contains \(n\) integers \(d_1, d_2, \dots, d_n\). Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) indicating that there is an edge between shops \(u\) and \(v\>.

Output: Output a single integer, which is the maximum total happiness Xiaocong can achieve by buying items subject to the above conditions.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (number of shops and total money). Following that are three lines:

• The first line contains \(n\) integers: \(w_1, w_2, \dots, w_n\) (the happiness value per unit for each shop).
• The second line contains \(n\) integers: \(c_1, c_2, \dots, c_n\) (the cost per unit for each shop).
• The third line contains \(n\) integers: \(d_1, d_2, \dots, d_n\) (the maximum number of items available in each shop).

Then follow \(n-1\) lines, each containing two integers \(u\) and \(v\) which denote an edge between shop \(u\) and shop \(v\). The shops are 1-indexed.

outputFormat

Output a single integer representing the maximum total happiness Xiaocong can achieve.

sample

3 10
1 2 3
2 3 4
2 1 2
1 2
1 3

6