Perfect Sets and Test Device Placement

We are given a tree with N nodes. Each node i has a weight w_i and a value v_i. The tree is weighted (i.e. every edge has an associated length).

A connected subset S of nodes is called feasible if the sum of the weights of its nodes does not exceed a given integer M, that is, \(\sum_{i\in S}w_i \le M\). Among all feasible connected subsets, only those whose total value \(\sum_{i\in S}v_i\) is maximum are considered. Such a subset is called a perfect set.

Now, you are also given an integer K. Small A wants to choose K distinct perfect sets for testing. Before starting the tests, he must choose a node x on which to place his test device. The device has a maximum power (Max). In each test, for the chosen perfect set S, an energy transmission is attempted from x to every node y in S. The required energy for node y is:

[ energy(x,y) = dist(x,y) \times v_y, ]

where \(dist(x,y)\) is the shortest distance (sum of edge lengths) between nodes \(x\) and \(y\) in the tree. The test on S fails if either:

• x is not in \(S\), or
• There is at least one \(y \in S\) with \(dist(x,y)\times v_y > Max\).

The chosen K perfect sets (for testing) are called testable if there exists at least one node \(x\) that can serve as the device placement for all of them – that is, for each chosen set \(S\), we have \(x \in S\) and \(\forall y \in S,\; dist(x,y)\times v_y \le Max\).

Your task is to count the number of ways to choose K perfect sets (from all perfect sets) such that they are testable. Output the answer modulo

[ 11920928955078125. ]

inputFormat

The input begins with a line containing four integers:

1. N (the number of nodes)
2. M (the maximum total weight allowed for a set)
3. K (the number of perfect sets to choose)
4. Max (the maximum power of the test device)

The second line contains N integers: w₁, w₂, ..., w_N, representing the weights of the nodes.

The third line contains N integers: v₁, v₂, ..., v_N, representing the values of the nodes.

Each of the next N-1 lines contains three integers u v d, indicating that there is an edge between nodes u and v with length d.

It is guaranteed that the given graph forms a tree.

outputFormat

Output a single integer – the number of ways to choose K testable perfect sets modulo \(11920928955078125\).

sample

3 6 1 10
1 2 3
4 5 6
1 2 1
2 3 2

0