题目背景
Daleva Geoge是一个热爱生活的园艺工。
题目描述
Daleva Geoge的花园里有一颗常年没有修剪的树,这一天,Daleva Geoge家里来了客人,为了给客人一个好印象,他需要整理这个花园,但是那一颗树显得太碍眼了,他必须要给他好好地修剪一下。
这是一颗以root为根的有根树,有n个节点。Daleva Geoge在根节点,Daleva Geoge对某些叶子的形态感到不满,需要剪去多余的枝条。
有S个需要修剪的叶子节点,这些叶子节点有一些多余的枝条,这些叶子节点有着自己的权值ai,表示这个节点上有多少个Daleva Geoge不需要的枝条。同时,因为花园里没法容下这些枝条(否则就变得不和谐了),Daleva Geoge需要把这些枝条安装到某些节点上。
Daleva Geoge有一个神奇的胶水和一把神奇的剪刀,因此你不需考虑每个树枝的固定形态,根据Daleva Geoge的推测,一共有T个叶子节点需要安装这些枝条,这些节点有各自的权值bi,表示需要bi个枝条才能把这棵树变得很好看。
为了修剪好这棵树,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,ai,表示在第x个节点有ai个多余枝条,数据保证x为叶子节点。
接下来T行,每行两个整数:x,bi,表示在第x个节点需要bi个枝条,数据保证x为叶子节点。
数据保证∑i=1Sai=∑i=1Tbi
输出格式
一行,一个整数,表示Daleva Geoge最少需要跑多长的路才能把树修剪好并回到树根爬下树。
提示
样例1解释:

蓝色数字表示有多少多余枝条,黄色数字表示需要的枝条数。
则最优方案为:1→2→1→3→1→2→1→3→1→4→1→2→1→4→1,答案为40;
对于5%的数据,为样例1。
对于40%的数据,n≤10,G≤10;w≤1000
对于100%的数据,n≤40,0000,G≤1000;S+T≤n;ai,bi≤109;w≤109
数据保证不会有任意一个叶子节点既需要枝条又有多余枝条。