Problem Description

Little A has a weighted tree with $N$ nodes. Each node has a weight $w_i$ and a value $v_i$.

Now Little A wants to select some nodes to form a set $S$, such that the total weight of these nodes is $\leq M$ and they form a connected component. Little A is a perfectionist, so he will only choose those $S$ with the maximum possible total value among all sets that satisfy the conditions. We call such a set $S$ a perfect set.

Now Little A wants to choose $K$ sets from all perfect sets, and test these $K$ perfect sets separately. Before these $K$ tests begin, Little A first needs a node $x$ to place his testing device, whose maximum power is $Max$.

In each subsequent test, Little A will transmit energy once to all nodes in the test object $S$. The power required to transmit energy to a node $y$ is $dist(x,y)\times v_y$, where $dist(x,y)$ denotes the length of the shortest path between nodes $x$ and $y$ on the tree. Therefore, if there exists a node $y$ in $S$ such that $dist(x,y)\times v_y>Max$, the test will fail. At the same time, in order to ensure stable energy transmission, the node $x$ where the device is placed must be in the set $S$, otherwise the test will also fail.

Now Little A wants to know: how many ways are there to choose $K$ sets from all perfect sets, such that he can find a node to place the testing device and complete his tests?

You only need to output the number of ways modulo $11920928955078125$.

Input Format

The first line contains four positive integers, denoting $N,M,K,Max$.

The next line contains $N$ positive integers, denoting $w_1,\dots,w_N$.

The next line contains $N$ non-negative integers, denoting $v_1,\dots,v_N$.

The next $N-1$ lines each contain three positive integers $A_i,B_i,C_i$, meaning there is an edge of length $C_i$ connecting nodes $A_i,B_i$ in the tree.

Output Format

One number, denoting the number of ways modulo $11920928955078125$.

7 3 2 4
1 1 2 2 1 2 2
1 1 1 2 1 2 2
1 2 1
1 3 2
1 4 2
2 5 1
2 6 2
4 7 3

2

Hint

Sample Explanation

The perfect sets are $\{1,2,5\},\{1,4\},\{2,6\}$.

The ways to choose $K$ sets from them and still complete the tests are: choosing $\{1,2,5\},\{1,4\}$, or choosing $\{1,2,5\},\{2,6\}$.

Constraints

For $100\%$ of the testdata: $N\leq 60$, $M\leq 10000$, $C_i\leq 10000$, $K,w_i,v_i\leq 10^9$, and $Max\leq 10^{18}$.

Translated by ChatGPT 5