Mohsen 最近因为经济困难换了工作，成为了一名出租车司机。他住在 Amol 市。这座城市可以看作是一个包含 $n$ 个顶点和 $m$ 条边的无向图，Mohsen 的家位于顶点 $h$。图中的每条边都有一个权重，表示 Mohsen 开车通过该边所需的时间（单位为秒）。由于经济状况不佳，Mohsen 向 Bahram 请教如何通过这份工作赚取更多收入。

Bahram 告诉 Mohsen，他掌握了未来一天内所有的乘客预约请求，并告诉他，如果预先知道这些请求，Mohsen 就能获得最大收益。具体来说，Bahram 告诉他未来一天内有 $k$ 个预约请求，第 $i$ 个请求在时间 $t_i$ 发出，起点为 $s_i$，终点为 $d_i$。此外，Mohsen 完成该请求可获得 $val_i$ 的收入。Mohsen 只有在请求发出时身处 $s_i$ 才能接受该请求。他可以在两次行程之间在任意顶点休息，并且可以在起点和终点之间选择任意路径。Mohsen 早上 $07:00:00$ 出门，晚上 $23:00:00$ 前必须回到家。在收到这些信息后，Mohsen 不知道如何利用这些信息来增加收入，但他确信 Bahram 的建议一定会对他有所帮助。因此，他请求你根据 Bahram 提供的信息，帮助他计算出一天内能获得的最大收入。

输入格式

第一行包含四个整数 $n, m, k, h$，分别表示图的顶点数、边数、预约请求数以及 Mohsen 家所在的顶点编号。接下来的 $m$ 行描述图的边，第 $i$ 行包含 $u, v, dis_i$，表示 $u$ 和 $v$ 之间存在一条长度为 $dis_i$ 的边。

最后 $k$ 行描述预约请求，每行包含 $s_i, d_i, val_i$ 以及请求时间（格式为 $hh:mm:ss$），分别表示请求的起点、终点、收入以及请求发出的时间。

输出格式

在唯一的一行中输出 Mohsen 可以获得的最大金额。

数据范围

• $1 \le n \le 500$
• $1 \le u, v, s_i, d_i, h \le n$
• $1 \le m \le n \times (n - 1) / 2$
• $1 \le k \le 2000$
• $1 \le dis_i, val_i \le 10^5$

样例

输入 1

5 4 3 1
1 2 3600
2 3 3600
3 4 3600
4 5 3600
1 3 10 08:00:00
2 4 30 11:00:01
4 5 40 11:30:00

输出 1

50

输入 2

4 6 5 1
1 2 1800
2 3 1800
3 4 1800
4 1 1800
1 3 3800
2 4 3300
1 3 10 08:15:00
2 4 15 07:36:00
3 1 20 09:00:00
1 4 15 10:00:00
4 3 100 22:15:00

输出 2

35