You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

⼩H 在今年有 m 次跨国商务，每次需要从 dj 站到 ej 站（如果 dj = ej 可以视作不需要乘车）。

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

输入格式

第—行两个正整数 n, m 。

接下来 n -1 行，每行三个正整数表示 ai , bi , ci 。 接下来 m 行，每行两个正整数，表示 dj 和 ej 。

输出格式

—个正整数，表示小H 花费的最少价格。

输入输出样例

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

27

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

51

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

16

数据范围

对于100%的数据： 1 ≤ ai , bi , ci ≤ 10^3 。