Little A has a tree with $N$ nodes, where each edge has a weight. Each node $i$ has a weight $w_i$ and a value $v_i$.

Little A wants to select a subset of nodes $S$ such that the sum of weights of the nodes in $S$ is $\leq M$ and the nodes in $S$ form a connected subgraph. Little A is a perfectionist, so he will only choose those sets $S$ that have the maximum possible sum of values. We call such a set $S$ a perfect set.

Now, Little A wants to choose $K$ perfect sets from all possible perfect sets and perform a test on each of these $K$ sets. Before these $K$ tests begin, Little A must first choose a node $x$ to place his testing device, which has a maximum power capacity of $Max$.

In each subsequent test, Little A performs an energy transmission 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$ in the tree. Therefore, if there exists a node $y$ in $S$ such that $dist(x,y) \times v_y > Max$, the test fails. Additionally, to ensure the stability of the energy transmission, the node $x$ where the testing device is located must be in the set $S$; otherwise, the test also fails.

Little A wants to know how many ways there are to choose $K$ perfect sets from all perfect sets such that he can find a node $x$ to place his testing device to complete all his tests.

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

Input

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

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

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

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

Output

A single integer representing the number of ways modulo $11920928955078125$.

Examples

Input 1

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

Output 1

2

Note 1

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

The ways to choose $K$ sets that can complete the test are choosing $\{1,2,5\}, \{1,4\}$ or choosing $\{1,2,5\}, \{2,6\}$.

Subtasks

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