Cheapest Tolls Before the Deadline

A courier must get from depot src to customer dst within limit minutes. Roads are undirected: roads[i] = [u, v, minutes, toll] takes minutes (at least 1) and charges toll. Roads may be reused.

Return the minimum total toll of a route that arrives at dst after at most limit minutes, or -1 if no route is fast enough.

Examples

Input:  n = 3, roads = [[0,1,2,1],[1,2,2,1],[0,2,3,10]], src = 0, dst = 2, limit = 4
Output: 2
Explanation: 0 -> 1 -> 2 takes 4 minutes and costs 2.

Input:  same roads, limit = 3
Output: 10
Explanation: only the direct road is fast enough.

Input:  same roads, limit = 2
Output: -1

Constraints

• 1 <= n <= 200, 0 <= len(roads) <= 500, 1 <= limit <= 500
• 1 <= minutes <= 500, 0 <= toll <= 10**4
• Target O(limit * E) time.

Goals

• Recognise that two edge weights (time and toll) break plain Dijkstra
• Build a DP over (elapsed time, node) using positive travel times
• Take the best toll over every arrival time within the limit