B

C哥建立了一条横跨全球的铁路，方便有长期跨国需求的人通勤。这条铁路有$n$个站点，从$1$到$n$编号，$n-1$ 条线路，其中第$i$ 条线路在第$i$号站与第$i+1$号站之间通行，单次乘坐需要花费$a_i$元。

除此之外，还可以选择办理 VIP 卡， $n-1$ 条线路的 VIP 系统是独立的，在第$i$号站与第$i+1$号站之间的路线办理 VIP 需要支付$b_i$元，成为 VIP 以后，每次只需要支付$c_i$元即可在$i$号站与第$i+1$号站之间通行。

大G在今年有$m$次跨国商务，每次需要从$d_j$站到$e_j$站（如果 $d_j=e_j$ 可以视作不需要乘车）。

大G想让你帮它算算，最少花多少钱能完成今年的通勤。

第一行两个正整数$n$，$m$。

接下来$n-1$行，每行三个正整数表示$a_i,b_i,c_i$。

接下来$m$行，每行两个正整数，表示$d_j$和$e_j$。

一个正整数，表示大G花费的最少价格。

【样例 1 输入】

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

【样例 1 输出】

27

【样例 2 输入】

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

【样例 2 输出】

51

【样例 3 输入】

5 1
6 2 5
1 2 8
8 7 3
9 1 6
2 5

【样例 3 输出】

16

其余样例见下发文件。

对于$100\%$的数据：$1 \leq a_i,b_i,c_i \leq 10^3$。