Fastest Route in Rush Hour

A route that takes 20 minutes at 10:00 can take an hour at 08:30. A navigation app that ignores the time of day sends people straight into traffic jams. You are writing the core of a planner that knows when each road is congested.

The city has n intersections, numbered 0 to n - 1, joined by one-way roads. Road i is roads[i] = [from, to, base, rushStart, rushEnd, rushTime]. A car that enters the road at minute t takes:

• rushTime minutes when rushStart <= t < rushEnd (the road's rush window);
• base minutes otherwise.

Only the minute the car enters a road matters: entering one minute before the rush window takes base minutes even if the drive overlaps the window. A road with rushStart == rushEnd has no rush window. Drivers may wait at any intersection for as long as they like before entering the next road.

The driver leaves intersection source at minute departure. Return the earliest minute at which they can arrive at target, or -1 if no route reaches it.

Example

n = 4, departure = 480 (08:00), from 0 to 3, with roads [0,1,10,480,540,40], [1,3,10,0,0,10], [0,2,15,0,0,15] and [2,3,15,0,0,15].

The road from 0 to 1 is in its rush window until 09:00. Driving it now takes 40 minutes; waiting for 09:00 and then taking 10 arrives even later. Through 1 the car reaches 3 at minute 530. Through 2 it reaches 3 at 480 + 15 + 15 = 510, which is the answer.