Problem Background

$Daleva$ $Geoge$ is an avid gardener who loves life.

Problem Description

$Daleva$ $Geoge$'s garden has a tree that has not been pruned for years. Today, guests are coming to his home, and to make a good impression, he needs to tidy up the garden. However, the tree is too conspicuous and needs to be pruned properly.

This is a rooted tree with $n$ nodes, rooted at $root$. $Daleva$ $Geoge$ is at the root node. He is dissatisfied with the appearance of some leaf nodes and needs to remove excess branches.

There are $S$ leaf nodes that need pruning. These leaf nodes have excess branches, each with a weight $a_{i}$, indicating how many unwanted branches are at that node. Additionally, since the garden cannot accommodate these branches (otherwise it would become unsightly), $Daleva$ $Geoge$ needs to install these branches on other nodes.

$Daleva$ $Geoge$ has a magical glue and a magical pair of scissors, so you do not need to consider the fixed shape of each branch. According to $Daleva$ $Geoge$'s estimation, there are $T$ leaf nodes that need these branches, each with a weight $b_{i}$, indicating how many branches are needed to make the tree look good.

To prune the tree properly, $Daleva$ $Geoge$ has to traverse the tree, cutting the excess branches from each leaf node and gluing them onto other leaf nodes that need them. Each edge has a different length. Given the size of the tree, $Daleva$ $Geoge$ needs to know the minimum distance he has to travel to prune the tree and return to the root.

Although $Daleva$ $Geoge$ has these magical tools, his pocket capacity is limited to $G$. $Daleva$ $Geoge$ cannot carry too many branches at once, i.e., not more than $G$. This makes him reluctant to consider these tedious details. $Daleva$ $Geoge$ can certainly calculate it, but he wants to conserve his energy for pruning, so this arduous task falls on you.

$Daleva$ $Geoge$ has already told you the shape of the tree in his mind, and he will be watching from his chair to see how you solve these problems.

Input Format

The first line contains three integers: $n, G, root$.

The next $n-1$ lines describe each tree edge, with each line containing three integers: $u, v, w$, indicating an edge between $u$ and $v$ with length $w$.

The next line contains two integers: $S, T$.

The next $S$ lines, each containing two integers: $x, a_{i}$, indicating that the $x$-th node has $a_{i}$ excess branches. The data guarantees that $x$ is a leaf node.

The next $T$ lines, each containing two integers: $x, b_{i}$, indicating that the $x$-th node needs $b_{i}$ branches. The data guarantees that $x$ is a leaf node.

The data guarantees that $\sum_{i=1}^{S}a_{i} = \sum_{i=1}^{T}b_{i}$.

Output Format

A single line containing an integer, representing the minimum distance $Daleva$ $Geoge$ needs to travel to prune the tree and return to the root.

Sample Input and Output

Input Sample #1

4 2 1
2 1 4
4 1 2
3 1 2
1 2
2 6
3 3
4 3

Output Sample #1

40

Input Sample #2

5 1 1
1 2 2
3 2 2
4 1 2
5 4 2
1 1
3 1
5 1

Output Sample #2

16

Input Sample #3

20 10 18
1 17 86406
17 16 94583
19 10 28177
16 18 31981
10 14 36241
1 7 28919
2 1 94673
5 6 2801
7 11 81927
11 13 7779
17 5 71948
19 7 20264
1 8 17736
13 20 97181
17 9 16807
11 15 93705
17 3 29601
1 12 43829
13 4 27537
1 6
20 23585
9 8376
12 3128
15 5417
8 4011
3 1156
6 1497

Output Sample #3

1289613990

Notes

Sample 1 Explanation:

Blue numbers indicate the number of excess branches, and yellow numbers indicate the number of branches needed.

The optimal solution is: $1→2→1→3→1→2→1→3→1→4→1→2→1→4→1$, with an answer of $40$.

For $5\%$ of the data, it is the same as Sample 1.

For $40\%$ of the data, $n \leq 10, G \leq 10; w \leq 1000$.

For $100\%$ of the data, $n \leq 40,0000, G \leq 1000; S + T \leq n; a_{i}, b_{i} \leq 10^{9}; w \leq 10^{9}$.

The data guarantees that no leaf node will both need branches and have excess branches.

见题面 Input 部分

见题面 Output 部分