题目描述

在清华园里，有 $n$ 幢宿舍楼。共有 $n-1$ 条无向道路，每条道路连接两座宿舍楼，任意两座宿舍楼都相互连通，所以清华园的所有宿舍楼和无向道路构成一棵树。清华园里的同学们日常有两种出行方式，分别是步行和骑自行车。在一些平坦的道路上，骑自行车会是一个不错的选择；但在一些比较崎岖的路上，选择步行的方式则更加明智。第 $i$ 条道路有两个属性值，分别是 $a_i,b_i$，其中 $a_i$ 表示骑自行车通过这条道路的代价，$b_i$ 表示步行通过这条道路的代价。需要注意的是，为了维护交通秩序，校规规定任何人不得在道路中间更换出行方式，也就是说一个人要么骑自行车通过整条道路，要么步行通过整条道路。当然，在通过整条道路到达下一幢宿舍楼后，更换出行方式就是被允许的了。

每个同学都会对两种出行方式有所偏好，特别地，住在同一幢宿舍楼的同学的偏好是相同的。具体而言，第 $i$ 幢宿舍楼的同学有两个属性值 $c_i,d_i$，表示每骑自行车经过一条道路会额外支付 $c_i$ 的代价，每步行经过一条道路会额外支付 $d_i$ 的代价。举个例子，R 同学的偏好值为 $c=7,d=3$，有一条道路的属性值为 $a=2,b=10$，那么如果他选择骑车，那么花费的代价是 $7+2=9$，他选择步行花费的代价是 $3+10=13$，所以他会骑车通过这条道路，最后花费的代价是 $9$。需要注意的是，他每通过一条道路都可以重新选择一次出行方式，所以他在经过每条道路时都会选择代价较小的出行方式。

现在，对于所有的 $1\le i \le n,1\le j \le n,i\neq j$，都有一个 $i$ 号宿舍楼的人要去 $j$ 号宿舍楼玩，他的出行代价为他在所经过的所有道路上支付的代价和。求这些人的最小出行代价之和。输出答案除以 $10^9+7$ 所得的余数。

输入格式

第一行一个正整数 $n$ 和一个字符串 $type$，分别表示宿舍楼的数量和数据的类型。$type$ 字符串是为了能让大家更方便地获得部分分，你可能不需要用到这个输入。其具体含义在【子任务】中有解释。

第二行 $n$ 个正整数，第 $i$ 个正整数表示 $c_i$，即 $i$ 号宿舍楼的人每骑车通过一条道路花费的额外代价。

第三行 $n$ 个正整数，第 $i$ 个正整数表示 $d_i$，即 $i$ 号宿舍楼的人每步行通过一条道路花费的额外代价。

接下来 $n-1$ 行每行四个正整数 $u,v,a_i,b_i$，表示 $u,v$ 之间有一条边，这条边骑车代价为 $a_i$，步行代价为 $b_i$。

对于所有的输入数据，都有 $100\le n \le 5\times 10^5,1\le a_i,b_i,c_i,d_i\le 10^5,1\le u,v\le n$，保证输入的图为一棵树。

输出格式

输出一行一个整数，表示最终答案除以 $10^9+7$ 的余数。

4 A0
2 3 9 5
6 6 1 8
1 2 1 7
1 3 10 2
2 4 8 5

143

1号宿舍的人 $c=2,d=6$，所以以2为目的地的人最小代价为 $\min\left\{2+1,6+7\right\}=3$，以4为目的地的人最小代价为 $3+\min\left\{2+8,6+5\right\}=13$，以3为目的地的人最小代价为 $8$。总代价为 $24$。

2号宿舍以1为目的地的人最小代价为 $4$，以3为目的地的人最小代价为 $12$，以4为目的地的人最小代价为 $11$。总代价为 $27$。

3号宿舍以1为目的地的人最小代价为 $3$，以2为目的地的人最小代价为 $11$，以4为目的地的人最小代价为 $17$。总代价为 $31$。

4号宿舍以1为目的地的人最小代价为 $19$，以2为目的地的人最小代价为 $13$，以3为目的地的人最小代价为 $29$。总代价为 $61$。

将上面这些代价加和得总答案为 $143$。

子任务

本题共有 8 个子任务。各测试点分值及约定如下：

数据类型的含义：

大写字母约定了树的形态：

A：无特殊约定；

B：$i$ 号宿舍与 $i+1$ 号宿舍相连，即每一条边都满足 $v=u+1$；

数字约定了权值的特殊性质：

0：无特殊约定；

1：满足 $c_i=d_i,\forall 1\le i\le n$；

在提交代码后将为你评测预测试数据并返回结果。本题的预测试数据包含 ${{ tl.len(prob.pre_cases) }}$ 个测试点，分别按顺序对应各个子任务的数据范围。

注意：预测试数据的评测结果与最终评测结果没有关系。