Traffic Light Navigation

X is in city Z which has n intersections and m bidirectional roads. For each road i, the road connects intersections u_i and v_i. When X traverses road i, if no speed limit is set then it takes p_i seconds. However, if a speed limit is applied then it takes q_i seconds. The mayor will add speed limits on exactly k roads, and X is allowed to choose which roads get the speed limit.

Moreover, every intersection is equipped with a traffic light. For the ith intersection, the traffic light follows a cycle: green for \(x_i\) seconds, yellow for \(y_i\) seconds, and red for \(z_i\) seconds, then repeats. At any intersection, if the light is not red, X can depart immediately toward another intersection. Note that if X arrives exactly at the moment the light changes, the new color is taken into account. Also, if X departs when the light is yellow, it counts as having run a yellow light; he may run yellow lights at most g times during his journey. If the yellow limit is reached when the light is yellow, he must wait until the next green phase.

Initially, at time 0, all traffic lights switch to green simultaneously. At this moment, X starts at intersection 1 and wishes to reach intersection n in minimum time. Determine the least amount of time required for X to travel from intersection 1 to intersection n given he can choose where to apply the speed limits and his route accordingly.

inputFormat

The input is given as follows:

n m k g
x₁ y₁ z₁
x₂ y₂ z₂
... (n lines in total)
 u₁ v₁ p₁ q₁
 u₂ v₂ p₂ q₂
... (m lines in total)

All numbers are positive integers. It is guaranteed that there is a path from intersection 1 to intersection n.

outputFormat

Output a single integer: the minimum time required for X to travel from intersection 1 to intersection n.

sample

2 1 1 1
3 2 3
3 2 3
1 2 10 5

5