题目描述

月兔国由 $N$ 座城市和 $N-1$ 条道路组成。任意两座城市之间都可以通过道路互相到达，因此整个国家构成一棵树。

每条道路都有一个正整数长度。两座城市之间的距离，是连接它们的唯一简单路径上所有道路长度之和。

旅游部门准备选择两座城市 $X$ 和 $Y$ 建立旅游友好城市关系。

设两座城市的距离为 $D(X,Y)$，城市 $X,Y$ 的人口分别为 $C_X,C_Y$，则可获得的交通费收入为

共有 $Q$ 个相互独立的计划。每个计划给出：

• 城市 $X$ 的候选集合 $A$；
• 城市 $Y$ 的候选集合 $B$；
• 本次计划中每个候选城市的人口数。

集合 $A$ 与 $B$ 不相交。不同计划中的人口数彼此独立，不会永久修改城市信息。

对于每个计划，选择

使交通费收入最大，并输出最大值。

输入格式

第一行包含两个整数 $N,Q$。

接下来 $N-1$ 行，每行包含三个整数 $u,v,d$，表示城市 $u$ 和 $v$ 之间有一条长度为 $d$ 的道路。

随后依次输入 $Q$ 个计划。每个计划格式如下：

第一行包含两个整数 $N_A,N_B$，分别表示集合 $A$ 和集合 $B$ 的大小。

接下来 $N_A$ 行，每行包含两个整数 $u,p$，表示城市 $u\in A$，且本次计划中其人口为 $p$。

接下来 $N_B$ 行，每行包含两个整数 $v,q$，表示城市 $v\in B$，且本次计划中其人口为 $q$。

人口满足

同一计划中，$A$ 与 $B$ 不相交。

保证所有计划的候选城市总数满足

输出格式

对每个计划输出一行，表示能够获得的最大交通费收入。

样例 1

输入

3 3
1 2 1
2 3 1
1 2
1 1
2 2
3 3
1 2
2 2
1 1
3 3
1 2
3 3
1 1
2 2

输出

8
5
8

样例 2

输入

7 1
1 2 10
3 4 1
4 5 1
2 4 6
4 6 6
6 7 10
3 3
1 1
2 3
3 5
5 5
6 3
7 1

输出

102

样例说明

在样例 2 中，选择 $X=3,Y=7$ 时，收入为

选择 $X=1,Y=5$ 也能取得相同最优值。