On Time

Statement:

Classes begin at 8:00 am at the University of Cienfuegos (UCf). Bob doesn't want to be late, but he doesn't want to wake too early either. There are several ways by which he could get to UCf from his home: he could walk or take a bus or a combination of both.

Using a map of the city of Cienfuegos, Bob has identified N locations he could visit on his way to the UCf including the latter and his home, some of which are bus stops. He named all of these locations with unique integer numbers from 1 to N; by default he named his home as 1 and the University as N. Bob can walk from location a to location b if there is a street connecting them. To measure the length of every street Bob used the time (in seconds) it takes to walk through it.  

Every bus serving in the city has a route, a starting time S and a periodicity T. A bus route can be represented as a sequence of unique locations on Bob's map: c1, c2, ..., cR; ci != cj for i != j. Every locations in this description it is a bus stop. The bus takes 1 second to move from ci to ci+1. At time S a bus stops in the location c1, after 1 second traveling stops in c2, and so forth until it reaches the last stop in cR. Also every T seconds (counting from time S) there is a bus in c1 starting the same operation. Note that a bus can start the route at S+T*k (in location c1, k as a Natural Number), while another bus from the same route haven't yet reached cR.

Bob have gathered all the information necessary, he needs to find out at what time (with the accuracy of a second) he can leave home in order to arrive the UCf before classes begin.

Input:

A line with the numbers N (2 ≤ N ≤ 104, locations in Bob's map), M (0 ≤ M ≤ 105, number of streets), B (0 ≤ B ≤ 102, number of bus routes)  and P (1 ≤ P ≤ 86399, time in seconds when classes begin).

Next M lines describing each street with the numbers ai, bi (1 ≤ ai,bi ≤ N), li (1 <= li <= 103); meaning that Bob can walk from ai to bi, or from bi to ai, in li seconds. Next B lines describing a bus with the numbers S, T, R, c1, c2, ..., cR (0 ≤ S,T ≤ 86399 , 2 ≤ R ≤ 10, 1 ≤ ci ≤ N); meaning that this bus route begins operating at time S, repeats every T seconds and goes through locations c1, c2, ... and finishes at cR.

Output:

Print a single integer, the greatest time (in seconds) when Bob have to leave home in order to arrive at the UCf before time P (when classes begin). If Bob needs to leave home the day before (negative time) just print "sleep at the UCf". You may assume that there is always a path from location 1 to N.

Example input:
6 7 1 480
1 2 5
2 4 30
4 6 15
2 3 20
4 5 15
3 5 10
5 6 5
105 20 3 2 4 5
Example output:
460
Explanation:
In the example, Bob leaves home at 460, reaches location 2 at 465 by walking, at 465 takes the bus from location 2 to location 4 and from location 4 to location 5, reaching 5 at 467, finally walks to the UCf (location 6) reaching there at 472. Classes begin at 480, so he got earlier.


Time and memory limit:

  • 1s
  • 64MB

Problem source: Caribbean Online Judge