在举办神奇的“泡泡杯”（Bubble Cup）的神秘国度“泡泡国”（Bubbleonia）中，矗立着一棵神秘的“泡泡树”（Bubble Tree）。这棵被施了魔法的树不仅仅是一株巨大的植物：它是一个巨大的房间迷宫，里面装满了魔法药水和强大的怪物。每个房间都相当于树结构中的一个节点，所有节点都连接在一个以“主房间”（Grand Chamber，即节点 1）为根的层次结构中。在这座充满奇迹的复杂迷宫的某处，我们英勇的英雄正打算积累尽可能多的力量。

我们的英雄在树中有着特定的移动方式：他可以移动到任何相邻的房间，但他必须始终向远离主房间（节点 1）的方向移动（即只能走向子节点）。进入房间 $i$ 时，他会遇到一瓶魔法药水，可以将他的力量值增加 $S_i$。但要注意：有些房间有可怕的怪物把守，英雄必须先战胜它们！击败房间 $i$ 的怪物会使英雄的力量值减少 $M_i$，这当然意味着在战斗开始时，英雄的力量值必须至少为 $M_i$。

这就是你需要提供帮助的地方：英雄面临多种不同的场景，需要他从不同的起点出发，并以不同的初始力量值在泡泡树中穿行。你的任务是引导他，使他在每个场景结束时都能获得尽可能高的力量值。需要特别注意的是，每个场景都是相互独立的：在一次旅程中饮用的药水和消灭的怪物不会带入下一次旅程。

此外，在每个场景中，英雄在指定的房间 $A_i$ 开始他的冒险，初始力量值为 $X_i$。他可以选择留在起点房间，甚至立即退出这棵树，从而保持他的初始力量值。如果他决定继续前进，且起点房间有怪物把守，英雄必须在饮用魔法药水之前先击败这个守护者。在克服了这道初始障碍后，他可以移动到相邻的房间，目的是最大化他的最终力量值。他可以在旅程的任何一点停止；然而，最终目标是最大化他的终点力量值。

输入格式

第一行包含两个整数 $N$ 和 $Q$：分别表示泡泡树中的节点（房间）数和询问（场景）数（$1 \le N, Q \le 10^5$）。

接下来的 $N-1$ 行，每行包含两个整数 $U$ 和 $V$：表示由一条边相连的两个节点（$1 \le U, V \le N$，$U \ne V$）。保证生成的图是一棵树：即连通且无环、无自环或重边。

下一行包含 $N$ 个整数 $S_1, S_2, \dots, S_N$，其中 $S_i$ 表示房间 $i$ 中魔法药水所能提供的力量值（$0 \le S_i \le 10^9$）。

下一行包含 $N$ 个整数 $M_1, M_2, \dots, M_N$，其中 $M_i$ 表示击败房间 $i$ 中的怪物所需的力量值（$0 \le M_i \le 10^9$；如果 $M_i = 0$，则表示该房间没有怪物把守）。

最后 $Q$ 行，每行包含两个整数 $A_i$ 和 $X_i$，表示一个询问（场景）。英雄从房间 $A_i$ 开始旅程，初始力量值为 $X_i$（$1 \le A_i \le N$，$0 \le X_i \le 10^{14}$）。

输出格式

对于 $Q$ 个询问中的每一个，输出一行，包含一个整数，表示英雄在旅程结束时所能积累的最大力量值。请记住，英雄可以选择停在任何房间，甚至在进入起点房间之前就退出这棵树，但最终目标是最大化他的终点力量值。

样例

输入 1

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

输出 1

3
7
2

说明

以下是该样例的最优策略。

对于询问 1 ($1, 2$) 的策略：

1. 击败节点 1 的怪物（需要 1 点力量）。剩余力量：$2 - 1 = 1$。
2. 饮用节点 1 的药水（$+1$ 力量）。得到力量：$1 + 1 = 2$。
3. 移动到节点 3。
4. 击败节点 3 的怪物（需要 2 点力量）。剩余力量：$2 - 2 = 0$。
5. 饮用节点 3 的药水（$+3$ 力量）。最终力量：$0 + 3 = 3$。

对于询问 2 ($1, 5$) 的策略：

1. 击败节点 1 的怪物（需要 1 点力量）。剩余力量：$5 - 1 = 4$。
2. 饮用节点 1 的药水（$+1$ 力量）。得到力量：$4 + 1 = 5$。
3. 移动到节点 2。
4. 击败节点 2 的怪物（需要 3 点力量）。剩余力量：$5 - 3 = 2$。
5. 饮用节点 2 的药水（$+5$ 力量）。最终力量：$2 + 5 = 7$。

对于询问 3 ($2, 2$) 的策略：

1. 此时英雄唯一可行的选择是保持他的初始力量值。因为击败节点 2 的怪物需要 3 点力量，而英雄只有 2 点，所以他无法击败它。他也无法饮用该药水。最终力量为 2。