Conservative Bus Tours

Quido is running a bus travel agency in a remote mountainous area. Due to the difficult terrain the scheme of road connections between the villages is a tree. It means that there can be no circular tours in the area.
Let us suppose that a bus tour starts in village A and ends in village B. All villages on the (single) shortest route from A to B, including A and B, are called backbone villages of the tour.
A conservative tour from A to B is a tour which may visit more villages than just the backbone ones. The rule defining the conservative tour says that any village X visited during the tour is either a backbone village or it is directly connected to some backbone village by a single road with no other village between X and the backbone village. This rule implies that any backbone village, including the start and the end village of the tour, might be visited more than once during a conservative tour. The bus may leave a backbone village Y, travel to a neighbour non-backbone village, return to Y, drive to another neighbour non-backbone village, again return to Y and so on. After some number of visits to Y the bus has to move from Y to another backbone village Z closer to the end village. In Z, the scenario of multiple leaves and returns to the backbone village may be repeated, as well as in any subsequent backbone village closer to B (or even in B itself). Note that also the start village might play the role of Y.
Each non-backbone village can be visited only once during a conservative tour.
During a conservative tour, the bus never returns from a backbone village to another backbone village visited earlier.

Each village is assigned a special value called tourist index. The higher the tourist index the more turistically attractive the village is. The tour index of a conservative tour is the sum of the tourist indices of all villages visited during the tour, including the start and the end village of the tour. Each village tourist index is counted only once even if the bus visits the village more times. The agency strives to organize conservative tours with the highest possible tour indices.
The agency had assigned to each village one more number called the visit time. It is the time the tourists spend in the village when the bus arrives to the village for the first time during the tour. In all subsequent visits to the village the time spent in the village is considered to be 0 as the bus just quickly drives through the village, aiming for the next village in the itinerary.
Each road is assigned a number called ride time of the road. The number expresses the time it takes the bus to drive one way between the villages connected by the road. The time or the duration of a bus tour is the sum of visit times of all villages visited during the tour plus the ride times of all roads traversed during the tour. The ride time of each road is counted as many times as the bus traverses the road in the entire tour.

Image 1. A scheme of the villages and the roads in the area. The villages are shown as white circles labeled 0, 1, ..., 8. The roads are shown as straight lines between the villages. The blue value at a village denotes the village visit time, the blue value at a road denotes the ride time of the road. The tourist index of each village is shown in black on yellow background. Let 3 and 5 be the labels of the start and the end village of a bus tour. Let the maximum acceptable time of a bus tour be 140 time units. The dotted line follows the route of a conservative bus trip from village 3 to village 5 which lasts 135 time units and which tour index is 830. There is no conservative bus tour from village 3 to village 5 which would last at most 140 time units and which tour index would be higher than 830. (A conservative tour visiting villages 3, 4, 1, 4, 5, 8, 5, 1, 5, in this order, also lasts 135 time units and its tour index is 830 as well.) The image corresponds to Example 2 below.

The task

You are given a scheme of connections between the villages, the tourist indices and the visit times of all villages in the area. Furthermore, you are given the ride times of all roads connecting the villages. Also, you are given the start and the end village of a bus tour and the maximum acceptable time of a tour. Calculate the maximal possible tour index of all such conservative bus tour from the start village to the end village which last no longer than the given maximum acceptable time.

Input

The first input line contains four integers N, A, B, T separated by spaces. N is the number of villages in the area. The villages are labeled 0, 1, ..., N−1. A and B are labels of a tour start and end village. The value of T is the maximum acceptable time of a bus tour from A to B. The next line specifies the tourist index of each village. There are N values on the line. The k-th value on the line is the tourist index of the village labeled by k−1 (1 ≤ k ≤ N).
The next line specifies the visit time of each village. There are N values on the line. The k-th value on the line is the visit time of the village labeled by k−1 (1 ≤ k ≤ N).
The next N−1 lines are occupied by the list of the roads in the area. Each line describes one road connecting two neighbour villages. The line contains three numbers, the first two specify the labels of the villages and the third value specifies the ride time of the road between these two villages. The order of the roads in the list is arbitrary.
All time values in the input are given in the same time units.
It holds, 2 ≤ N ≤ 5×10⁵, 2 ≤ T ≤ 3×10⁵. Apart from the village labels, no other value in the input exceeds 10⁴.

Output

The output contains one text line with one integer denoting the maximal possible tour index of a conservative bus tour from A to B which lasts no longer than T. It is guaranteed that for each given input data there exists at least one conservative bus tour from A to B which lasts no longer than T.

8 3 7 71
150 190 180 120 130 140 170 160
8 7 8 4 5 8 2 11
0 4 1
1 5 9
2 6 3
6 7 9
5 6 2
4 5 7
3 4 3

900

9 3 5 140
180 120 150 100 130 160 190 140 170
20 15 20 5 5 5 5 10 15
0 3 35
1 4 10
2 5 5
3 4 10
4 5 20
3 6 30
4 7 40
5 8 5

830

Example 3

25 9  10 100
100 104 109 109 110 108 103 104 109 100 102 109 108 106 108 107 105 109 107 106 109 103 100 100 102
3 6 6 5 4 6 5 4 6 6 2 2 5 3 4 5 4 2 2 4 3 6 6 3 6
6 1 3
5 0 3
24 23 2
18 14 5
19 8 6
9 14 2
20 4 4
18 21 6
11 6 4
0 1 3
17 22 4
7 2 5
8 3 2
17 4 6
3 0 2
10 5 2
10 15 2
12 7 6
13 8 3
4 16 3
0 4 4
9 4 2
0 2 3
23 14 3

1171

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set