暂无测试数据。

题目背景

小G听说在一个迷宫里有宝藏！

这个迷宫一共有 $n$ 个节点，由 $n-1$ 条通道连接，其中宝藏在 $1$ 号节点。其中在若干个节点会被打通，有人会进入其中。他们同时会以每秒钟移动一个通道的速度向 $1$ 号节点移动。

在一开始的时候每个人都有一个热情度，当有两个人相遇的时候，热情度较小的那个会失去兴致，从而退出，热情度较大的那个因为看见有人退出，所以他的热情度会减去另一个退出的人的热情度的大小，然后继续移动。

宝藏只会在所有能到达 $1$ 号节点的人都到达了之后再打开。所以如果有人到达了 $1$ 号节点，但是还有人依旧没有失去兴致，那么他就会呆在 $1$ 号节点等待下一个人的到来。直到所有人都到达才结束。注意在 $1$ 号节点如果两个人相遇了也会让热情度更小的一个离开，让热情度更大的一个减去较小的那个然后留下来。

注意如果两个热情度相同的人相遇那么两个人就都会离开。

现在想求出最终在 $1$ 号节点获得宝藏的人的热情度。

题目描述

给定一棵有根二叉树，其中有若干个关键点有权值。开始时，每个关键点同时向上移动（可以理解为权值在移动），在某两个关键点相遇的时候，让权值较小的一个留下来（舍弃），另一个减去权值较小的那个继续向上移动。求最后根节点的值的大小。

每个关键点移动到根之后，如果没有其它点同时到达，那么它会停下来，等待下一个关键点到达根节点，直到最后一个能到达根节点的关键点到达后结束。

如果两个权值相同的点相遇，那么两个关键点就都会停下来（舍弃）。

保证根节点 $1$ 号节点只有一个儿子，且保证一定有人能拿到宝藏。

输入格式

第一行，一共两个整数 $n$ 和 $m$，分别表示节点总个数和有值的节点个数。

接下来 $n$ 行每行两个数 $ls_i,rs_i$，分别表示左右儿子的编号。若某个为零则表示没有该儿子。

接下来 $m$ 行，每行两个数 $x$ 和 $v$，表示编号 $x$ 的节点上有值为 $v$。

输出格式

一行，表示最终根节点的最后剩下的价值。

数据范围

对于 $20\%$ 的数据，$2\le n\le 20$。

另有 $20\%$ 的数据，$rs_i=0$。

另有 $20\%$ 的数据，除根节点外，其它的节点构成一棵满二叉树。

对于 $100\%$ 的数据，$2\le n\le 20000,2\le m\le n,1\le x\le n,0\le ls_i,rs_i\le n,1\le v\le 10^5$。

6 5
2 0
3 4
5 6
0 0
0 0
0 0
1 3
3 6
4 2
5 2
6 4

1

8 4
2 0
3 4
5 6
0 8
0 0
0 7
0 0
0 0
2 6
6 7
8 5
7 1

3