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,2,\cdots,n$ ，由 $m$ 条单向的公路连接。

第 $i$ 条公路从第 $a_i$ 个城市出发，前往第 $b_i$ 个城市，路程是 $d_i$ 米。

小 Z 决定从 $S$ 号城市出发，最终到达 $T$ 号城市（保证 $S\not =T$ ），并且你的车子初始速度 $v$ 为 $1$ 米每秒。

全国共有 $p\ (0\le p\le n)$ 个维修站，第 $i$ 个位于第 $x_i$ 个城市，小 Z 可以停留在这里花 $c_i$ 秒的时间将车升级，使得车速翻倍。小 Z 可以在某个维修站将车升级多次，但每次升级都会花 $c_i$ 秒的时间。例如，假设小 Z 当前的车速为 $v$，并且恰好在第 $x_i$ 个城市，那么他可以在第 $i$ 个维修站花 $3c_i$ 的时间将车升级三次，使得车速变为 $2\times 2\times 2\times v=8v$ 。

假设小 Z 的车速是 $v$ 米每秒，那么安全通过一条长度为 $d$ 米的公路所需的时间为 $\lceil\frac{d}{v}\rceil$ 秒（$\lceil x\rceil$ 代表最小的不小于 $x$ 的整数）。然而，有些公路是平整的，而另一些则是坑坑洼洼的。每当小 Z 通过一条坑坑洼洼的路，车的所有升级都会损耗，通过这条路之后车速会立即变回 $1$ 米每秒（但在通过这条路的过程中车速不会改变）。

现在小 Z 想知道，他到达 $T$ 号城市最少需要花多少秒？

输入格式

从 trip.in 文件读入数据。

第一行四个整数 $n,m,S,T$，代表城市个数，道路条数，起点城市编号，终点城市编号。

接下来 $m$ 行，每行三个整数 $a_i,b_i,d_i$ 和一个字符 $ch$ ( 只会是 G 或 B ），描述第 $i$ 条道路从第 $a_i$ 个城市出发，前往第 $b_i$ 个城市，路程是 $d_i$ 米，路况是 $ch$ 。如果 $ch$ 是 G 代表这条公路是平整的，否则是坑坑洼洼的。

接下来一行一个整数 $p$ ，代表维修站的个数。

接下来 $p$ 行，每行两个整数 $x_i,c_i$，代表第 $i$ 个维修站在第 $x_i$ 个城市，升级一次需要花 $c_i$ 秒。

输出格式

输出到 trip.out 文件。

输出一个整数，代表小 Z 到达 $T$ 号城市所需的最少秒数。如果小 Z 无法到达 $T$ 号城市，输出 $-1$。

样例

5 4 1 5 
1 2 4 G 
2 3 1 B
3 4 9 B
4 5 10 G 
1
1 1

23

样例 2

点击链接 ex_trip2.in 和 ex_trip2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于全部的数据，保证：

• $1 \leq n \leq 2 \times 10^4, 1 \leq m \leq 7 \times 10^4, 1 \leq S, T \leq n$

• $1 \leq a_i, b_i\leq n, 1 \leq d_i \leq 10^6$

• $0 \leq p \leq n, 1 \leq x_i \leq n, 1 \leq c_i \leq 10^6$

对于 $10\%$ 的数据，保证 $n=2,m=1$。

对于另外 $20\%$ 的数据，保证所有的 $d_i=1$ 。

对于另外 $20\%$ 的数据，保证 $p=0$ 。

对于另外 $20\%$ 的数据，保证 $d_i\le 100$ 。

对于剩下的 $30\%$ 的数据，没有特殊限制。