Search for the shortest path in a graph with variable weights

Go Hard maps

Task «Search for the shortest path in a graph with variable weights»

Given an undirected weighted graph of N vertices and M edges. Edge weights can change over time: for each edge, an initial weight and an array of changes (time moment and new value) are given. It is required to find the minimum path from vertex 1 to vertex N at time moment T. The path can go through any vertices, but edge weights are taken at time moment T. If no path exists, output -1.

Input Format

First line: N M T (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ T ≤ 10^9). Then M lines: u v w0 k (1 ≤ u,v ≤ N, 1 ≤ w0 ≤ 1000, 0 ≤ k ≤ 100) — edge, initial weight, number of changes. Then k lines: ti wi (0 ≤ ti ≤ T, 1 ≤ wi ≤ 1000) — time moment and new weight. The changes are sorted by ti.

Output Format

One integer — the minimum total weight of edges on a path from 1 to N at time T, or -1.

Examples

Example 1

INPUT

1 0
2 10 1
5

OUTPUT

5

main.go