U472918 小 Y 之面包车

小 Y 最近被某学校的信奥教练给挑上了，小 Y 对此十分开心，但有一个令人不怎么开心的点就是小 Y 的家离学校非常远，因此小 Y 就得每天早上早起坐面包车到学校门口，然后他就有个问题了。

小 Y 所乘坐的这个面包车在一个树形图上开着，一共有 $n$ 个节点，同时有 $k$ 个节点有客人，每一个客人都有自己的要求：$start_{i}$ 表示的就是第 $i$ 个客人要在 $start_{i}$ 这个地方上车；$end_{i}$ 表示的就是第 $i$ 个客人要在 $end_{i}$ 这个地方下车。 如果面包车司机能够将这个客人的要求满足的话，那么面包车司机就能得到相应的金钱 $v_{i,1}$，具体操作就是首先将面包车开到这个客人所在的位置，再将这个客人送到客人想要下车的位置，当然这个面包车司机到这个客人所在的位置一定要让这个客人上车。 但每一个客人又都有自己的时间限制 $time_{i}$。假如不能在规定时间送到目的地的话，那么客人就会向司机索要赔偿金，这时候司机就会损失赔偿金的金钱量 $v_{i,2}$。时间从客人上车开始计算。 面包车一开始的位置是节点 $p$，面包车司机每一个时间都可以选择开或不开。 现在小 Y 在想如果自己是一个面包车司机该怎么办才能在 $m$ 秒的限制下获得最大的金钱数。

第一行四个整数 $n,m,p,k$。 接下来的 $n - 1$ 行，每行两个整数 $a,b$，表示 $a,b$ 之间有一条边。 接下来的 $k$ 行，每一行五个整数 $start_{i},end_{i},time_{i},v_{i,1},v_{i,2}$，表示如题意。

输出最大的金钱数。

$1 \le a,b,p,k,start_{i},end_{i} \le n \le 10^4$ $1 \le time_{i},v_{i,1},v_{i,2},m \le 10^9$