时空限制

1.5S/512M

题目描述

姚掌柜，你有什么新年愿望？
我希望这题不要和沙威玛有关，还有不要和我有关。
『消失』

jiangly 从不吃沙威玛，所以他要解决以下这个问题：

apiadu 正在参加一场由 CF 皇帝赞助的单人马拉松比赛，比赛场地是一棵大小为 $n$ 的树，结点编号为 $1\dots n$。

有 $q$ 轮比赛，每轮比赛会给定起点和终点 $s_i,t_i$，apiadu 会从 $s_i$ 出发沿着唯一的简单路径前往 $t_i$，初始时，其拥有 $0$ 的体力。

每一个结点上还有一个太阳，假设 apiadu 当前在结点 $x$，则 apiadu 可以先进行体力补给：花费 $a_x$ star 受到 $1$ 次太阳照射，使体力恢复 $1$ 点，在一个结点可以多次受到太阳照射。

在 apiadu 体力补给结束后，其体力将减少 $w_x$（无论 apiadu 是否选择照射，其体力均会减少 $w_x$），如果体力小于 $0$，他将会失败。

现在，jiangly 希望 apiadu 在每轮比赛中都不会失败，由于 apiadu 不想花费过多的 star。故请对于每一轮比赛计算出 apiadu 所需的最少 star。

这个问题当然被 jiangly 秒了，所以你要解决这个问题。

格式

输入格式

第一行包含两个正整数 $n,q$，表示树的大小和比赛轮数。

第二行包含 $n$ 个正整数 $a_1,a_2 ,\cdots , a_n$。

第三行 $n$ 个正整数 $w_1,w_2 ,\cdots , w_n$。

第四行到 $n+2$ 行，第 $i+1$ 行两个正整数表示 $u_i,v_i$，表示 $u_i,v_i$ 之间有一条边。

第 $n+2$ 到 $n+q+1$ 行，第 $i+n+1$ 行两个正整数 $s_i,t_i$，表示每轮比赛的起点和终点。

输出格式

输出 $q$ 行，第 $i$ 行一个整数表示第 $i$ 轮的答案。

样例

样例输入 #1

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

样例输出 #1

6
12
8
2
18

样例输入 #2

5 6
3 2 4 3 3
5 9 5 9 7
1 4
3 4
5 3
3 2
4 5
1 2
1 3
2 3
3 1
5 1

样例输出 #2

63
75
57
28
62
78

样例输入 #3

20 10
370768 388228 927234 449838 822966 724169 981339 503746 442540 665081 549446 37996 891514 511093 671268 897014 478268 141905 965867 159326
493409 431191 299621 508503 451693 348931 457903 131720 296247 641414 563579 212427 851052 244996 429390 536431 778506 104597 562946 218295
3 15
15 16
18 6
13 5
6 10
4 19
18 17
11 8
4 5
8 13
12 2
14 10
14 9
12 1
7 19
3 2
7 17
20 9
16 20
4 19
1 11
19 11
16 10
15 11
18 6
2 12
8 1
4 1
3 16

样例输出 #3

481978475262
489546786344
1671271053568
704394195386
1552998450481
64357890840
175471795840
2291507867815
1568901861925
926143509342

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

Subtask No.	分值	$n=$	$q =$	特殊性质 A	特殊性质 B	子任务依赖
1	$20$	$2000$
2	$10$	$2\times 10^5$	$2 \times 10^5$	有	有
3	$10$					$2$
4	$20$			有
5	$40$					$1,2,3,4$

特殊性质 A：保证 $u_i=i,v_i=i+1$。

特殊性质 B：保证 $s_i=1$。

对于 $100\%$ 的数据，$1\le n,q,u_i,v_i,s_i,t_i \le 2\times 10^5,1\le w_i,a_i\le 10 ^6$。