Mohsen has recently changed jobs due to financial difficulties and has become a taxi driver. He lives in the city of Amol. The city is represented as an undirected graph with $n$ vertices and $m$ edges. Mohsen's house is located at vertex $h$. Each edge in this graph has a weight representing the time (in seconds) it takes for Mohsen to travel through it with his car. Due to his poor financial situation, Mohsen has gone to Bahram to get advice on how to earn more money from this job.

Bahram tells Mohsen that he knows all the ride requests for the next day and that by knowing them, Mohsen can maximize his income. Specifically, Bahram tells him that there are $k$ requests for the next day, where the $i$-th request is made at time $t_i$ at vertex $s_i$, and its destination is $d_i$. Mohsen will earn $val_i$ from this request. Mohsen can only accept a request if he is present at $s_i$ at the time of the request. He can also rest at any vertex between his trips and can choose any path between the origin and destination. Mohsen leaves his house at 07:00:00 in the morning and wants to return home by 23:00:00 at night. After receiving this information from Bahram, Mohsen does not know how this information helps him earn more money, but he is sure that Bahram's advice will help him as always. For this reason, he has asked for your help to earn the maximum daily income based on Bahram's information.

Input

The first line of the input contains four integers $n$, $m$, $k$, and $h$, representing the number of vertices in the graph, the number of edges in the graph, the number of requests, and the vertex number of Mohsen's house, respectively. The next $m$ lines contain the specifications of the graph edges. The $i$-th line contains $u$, $v$, and $dis_i$, representing an edge between $u$ and $v$ with length $dis_i$.

The next $k$ lines contain the specifications of the requests. Each line contains $s_i$, $d_i$, $val_i$, and the request time in the format hh:mm:ss, representing the starting point, destination, the money earned from the request, and the time the request is made.

Output

Print the maximum amount of money Mohsen can earn on a single line.

Constraints

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

Examples

Input 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

Output 1

50

Input 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

Output 2

35