P5140 树枝修剪

$Daleva$ $Geoge$是一个热爱生活的园艺工。

$Daleva$ $Geoge$的花园里有一颗常年没有修剪的树，这一天，$Daleva$ $Geoge$家里来了客人，为了给客人一个好印象，他需要整理这个花园，但是那一颗树显得太碍眼了，他必须要给他好好地修剪一下。 这是一颗以$root$为根的有根树，有$n$个节点。$Daleva$ $Geoge$在根节点，$Daleva$ $Geoge$对某些叶子的形态感到不满，需要剪去多余的枝条。 有$S$个需要修剪的叶子节点,这些叶子节点有一些多余的枝条，这些叶子节点有着自己的权值$a_{i}$,表示这个节点上有多少个$Daleva$ $Geoge$不需要的枝条。同时，因为花园里没法容下这些枝条（否则就变得不和谐了），$Daleva$ $Geoge$需要把这些枝条安装到某些节点上。 $Daleva$ $Geoge$有一个神奇的胶水和一把神奇的剪刀，因此你不需考虑每个树枝的固定形态，根据$Daleva$ $Geoge$的推测，一共有$T$个叶子节点需要安装这些枝条，这些节点有各自的权值$b_{i}$，表示需要$b_{i}$个枝条才能把这棵树变得很好看。 为了修剪好这棵树，$Daleva$ $Geoge$不得不在树上跑边，把每个叶子节点中多余的枝条剪下，并用胶水粘在其他的有需要的叶子节点上。每条边都有不同的长度，现在，由于树太过庞大，$Daleva$ $Geoge$需要知道，他最少需要跑多远的路才能使这棵树被修剪好，$Daleva$ $Geoge$也要回到树根上下来。 虽然$Daleva$ $Geoge$有这些神奇的工具，但他的口袋是有限的，容量为$G$,$Daleva$ $Geoge$不能一次带太多枝条，即不能超过$G$,这更使他懒于考虑这些繁琐的问题。$Daleva$ $Geoge$当然会算啦，他那么巨，但他为了养足精力去剪枝条，这一艰巨的任务就落在你身上了。 $Daleva$ $Geoge$已经把心中树的形状告诉你了，他要躺在椅子上看你怎么算这些问题。

输入的第一行$3$个整数：$n,G,root$. 接下来$n-1$行描述每个树边，每行$3$个整数：$u,v,w$表示$u$与$v$有一条长度为$w$的边。 接下来一行$2$个整数：$S,T$; 接下来$S$行，每行两个整数：$x,a_{i}$,表示在第$x$个节点有$a_{i}$个多余枝条，数据保证$x$为叶子节点。 接下来$T$行，每行两个整数：$x,b_{i}$,表示在第$x$个节点需要$b_{i}$个枝条，数据保证$x$为叶子节点。 数据保证$\sum_{i=1}^{S}a_{i}=\sum_{i=1}^{T}b_{i}$

一行，一个整数，表示$Daleva$ $Geoge$最少需要跑多长的路才能把树修剪好并回到树根爬下树。

样例1解释：  蓝色数字表示有多少多余枝条，黄色数字表示需要的枝条数。 则最优方案为：$1→2→1→3→1→2→1→3→1→4→1→2→1→4→1$，答案为$40$; 对于$5\%$的数据，为样例1。 对于$40\%$的数据，$n\leq 10,G\leq 10;w \leq 1000$ 对于$100\%$的数据，$n\leq 40,0000,G\leq 1000;S+T\leq n;a_{i},b_{i}\leq 10^{9};w\leq 10^{9}$ 数据保证不会有任意一个叶子节点既需要枝条又有多余枝条。