## 1. Abridged problem statement

There are `N ≤ 5` lanes. At time `t`, lane `i` has speed

\[
v_i(t)=b_i+a_i\sin(t+\delta_i),
\]

where `b_i > a_i`, so all speeds are positive. You start at time `0` in lane `1` and need to travel distance `d`. You may change from lane `x` to lane `y`; this takes `c * |x-y|` time, during which you do not move forward.

Output the minimum travel time and a chronological list of lane changes achieving it, with floating-point accuracy about `1e-6`.

---

## 2. Detailed editorial

### Distance traveled in one lane

If we stay in lane `L` from time `t` to `t + Δt`, the traveled distance is

\[
\int_t^{t+\Delta t} \left(b_L+a_L\sin(s+\delta_L)\right) ds.
\]

This integrates exactly to

\[
b_L\Delta t-a_L\left(\cos(t+\Delta t+\delta_L)-\cos(t+\delta_L)\right).
\]

So, given a starting time `t` and a distance `dx`, we can find the required driving time `Δt` by solving

\[
b_L\Delta t-a_L\left(\cos(t+\Delta t+\delta_L)-\cos(t+\delta_L)\right)=dx.
\]

Because `b_i > a_i`, speed is always positive, so the left side is strictly increasing in `Δt`. Therefore the equation has a unique solution.

---

### Discretizing distance

The solution uses a fine position grid:

```cpp
M = 200000
step = d / M
```

State:

```cpp
time_arr[i][L]
```

means: minimum known time to reach distance `i * step` and be in lane `L`.

Initial state:

```cpp
time_arr[0][0] = 0
```

because we start in lane `1`, internally stored as lane `0`.

---

### Transitions

At every distance grid point `i`, two types of transitions are considered.

#### 1. Lane changes at fixed position

Changing from lane `lp` to lane `L` costs

\[
c \cdot |L-lp|.
\]

No distance is traveled during a lane change.

For each pair of lanes:

```cpp
time_arr[i][L] = min(time_arr[i][L],
                     time_arr[i][lp] + c * abs(L - lp));
```

The code uses a snapshot `drive_arrival` of the times before lane-change relaxation. This is enough because `c * |x-y|` is a metric on lane indices, so chaining multiple lane changes at the same position is never better than directly changing to the final lane.

#### 2. Driving one distance step

From state `(i, L)`, drive `step` distance in the same lane:

```cpp
dt = drive_time(L, time_arr[i][L], step)
time_arr[i + 1][L] = time_arr[i][L] + dt
```

The function `drive_time` solves the integral equation using Newton iterations.

Because `step ≤ 1000 / 200000 = 0.005`, `dt` is small, so the solution avoids expensive `sin`/`cos` calls inside Newton by using Taylor expansions for `sin(dt)` and `cos(dt)`.

---

### Parent reconstruction

For every state, `par[i][L]` stores how it was reached:

- `-1`: start state,
- `L`: arrived by driving from position `i - 1`,
- another lane `lp`: arrived by switching from lane `lp`.

After the DP finishes, the best final lane is chosen among all lanes at distance `d`.

Then the parent pointers are followed backwards to recover:

- the sequence of lanes,
- approximate switch times.

---

### Why refinement is needed

The DP only allows lane changes at grid positions. The optimal lane-change position is continuous, not necessarily exactly on a grid point. A single switch may be off by a tiny amount, but with many switches the accumulated error can exceed `1e-6`.

So the solution refines switch times locally.

Suppose a switch goes from lane `A` to lane `B`, and the switch duration is

\[
c_k = c \cdot |A-B|.
\]

If the switch starts at time `t`, then the car arrives in lane `B` at time `t + c_k`.

At the local optimum, delaying or advancing the switch slightly should not improve the final answer. This gives the condition:

\[
v_A(t)=v_B(t+c_k).
\]

That is,

\[
b_A+a_A\sin(t+\delta_A)
=
b_B+a_B\sin(t+c_k+\delta_B).
\]

Each switch time is refined by Newton's method using this equation.

The Newton step is clamped to `[-0.3, 0.3]` to avoid jumping to the wrong periodic root.

---

### Exact final evaluation

After refinement, the solution recomputes the actual traveled distance along the schedule.

If the target distance is reached before some planned switch, the remaining switches are ignored.

For the final partial segment, the exact driving time is found by bisection using the exact integral formula, because the remaining time may be large and Taylor approximations are no longer reliable.

The solution evaluates both:

1. the original DP schedule,
2. the refined schedule,

and outputs the better one.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
double dist_total, c_change;
double a_arr[5], b_arr[5], delta_arr[5];

void read() {
    cin >> n >> dist_total >> c_change;
    for(int i = 0; i < n; i++) {
        cin >> a_arr[i] >> b_arr[i] >> delta_arr[i];
    }
}

double drive_time_exact(int lane, double t_start, double dx) {
    double a = a_arr[lane], b = b_arr[lane], d = delta_arr[lane],
           cos_t0 = cos(t_start + d), lo = (dx <= 0) ? 0.0 : dx / (b + a),
           hi = (a > 0 && dx > 0) ? dx / (b - a) : lo;
    if(hi < lo) {
        hi = lo;
    }

    for(int it = 0; it < 100; it++) {
        double mid = 0.5 * (lo + hi),
               f = b * mid - a * (cos(t_start + mid + d) - cos_t0) - dx;
        if(f > 0) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    return 0.5 * (lo + hi);
}

double drive_time(int lane, double t_start, double dx) {
    double a = a_arr[lane], b = b_arr[lane], d = delta_arr[lane],
           cos_t = cos(t_start + d), sin_t = sin(t_start + d),
           dt = dx / (b + a * sin_t);
    for(int it = 0; it < 4; it++) {
        double dt2 = dt * dt,
               cos_dt = 1.0 -
                        dt2 * 0.5 *
                            (1.0 - dt2 / 12.0 *
                                       (1.0 - dt2 / 30.0 * (1.0 - dt2 / 56.0))),
               sin_dt =
                   dt * (1.0 - dt2 / 6.0 *
                                   (1.0 - dt2 / 20.0 *
                                              (1.0 - dt2 / 42.0 *
                                                         (1.0 - dt2 / 72.0)))),
               cos_a = cos_t * cos_dt - sin_t * sin_dt,
               sin_a = sin_t * cos_dt + cos_t * sin_dt,
               f = b * dt - a * (cos_a - cos_t) - dx, fp = b + a * sin_a;
        dt -= f / fp;
    }
    return dt;
}

const int M = 200000;
double time_arr[M + 1][5];
int par[M + 1][5];

void solve() {
    // The solution roughly goes as finding a discretized path from the start
    // until distance D, and then locally adjusting it to smoothly do the
    // transitions. For the first part, we do a position-discretized DP on
    // states being (lane L, position-grid i) with step = d / M. We do
    // transitions (L, i-1) -> (L, i) the cost of which can be found by solving
    // the closed-form integral
    //
    //     b*dt - a*(cos(t+dt+d) - cos(t+d)) = step
    //
    // for dt by using Newton. v_L > 0 makes the LHS strictly monotone, and dt
    // <= step <= 5e-3 lets us replace cos(dt), sin(dt) with a 4-term
    // Taylor series so the inner loop is trig-free.
    //
    // Switch transition (Lp, i) -> (L, i) costs c * |L - Lp|; only direct
    // switches matter because c * |.| is a metric on the lane-index line.
    // par[i][L] is -1 at the start, L for a drive parent, or lp != L for a
    // switch parent.
    //
    // For the second stage of refinement, we have to do it because the DP only
    // places switches on grid points, leaving each switch time off by up to
    // step/(2*v). This is small per switch, but with up to ~100 switches in
    // tight tests the cumulative error exceeds the 1e-6 tolerance (without this
    // step we got WA on test 4). For each switch k from lane A to
    // lane B with switching duration c_k = c*|A-B|, the optimal switch
    // moment t_k is the one where
    //
    //     v_A(t_k) = v_B(t_k + c_k).
    //
    // Intuitively, at the optimum the speed we'd leave A with equals
    // the speed we'd arrive on B with, so delaying or advancing the
    // switch trades equal distance between the two segments and the
    // total drive needed on the final lane is unchanged. The condition
    // is independent across switches (it follows from a Lagrangian
    // argument: perturbing t_k by delta shifts adjacent-segment
    // distance by (v_A(t_k) - v_B(t_k + c_k))*delta, which must vanish
    // at a minimum of T_end), so a 1D Newton per switch suffices.
    // Steps are clamped to <= 0.3 to stay in the basin of the root the
    // DP identified; if Newton still lands on the wrong branch
    // (f' >= 0 at convergence marks a max of T_end rather than a min)
    // we revert that switch to its DP estimate. t_k is clamped
    // monotone so the schedule remains valid.
    //
    // The final segment's end time is solved by bisecting the same
    // integral (dt can now be large, so the Taylor version no longer
    // converges). As a safety net we compute T_end for both the
    // refined and the DP schedule and emit the smaller one: the DP
    // schedule covers exactly d by construction, so refinement can
    // only help.

    double step = dist_total / M;
    for(int L = 0; L < n; L++) {
        for(int i = 0; i <= M; i++) {
            time_arr[i][L] = 1e18;
            par[i][L] = -1;
        }
    }

    time_arr[0][0] = 0;

    double switch_cost[5][5];
    for(int L = 0; L < n; L++) {
        for(int lp = 0; lp < n; lp++) {
            switch_cost[L][lp] = c_change * abs(L - lp);
        }
    }

    for(int i = 0; i <= M; i++) {
        double drive_arrival[5];
        for(int L = 0; L < n; L++) {
            drive_arrival[L] = time_arr[i][L];
        }

        for(int L = 0; L < n; L++) {
            for(int lp = 0; lp < n; lp++) {
                if(lp == L) {
                    continue;
                }

                double cand = drive_arrival[lp] + switch_cost[L][lp];
                if(cand < time_arr[i][L]) {
                    time_arr[i][L] = cand;
                    par[i][L] = lp;
                }
            }
        }

        if(i < M) {
            for(int L = 0; L < n; L++) {
                double t = time_arr[i][L], dt = drive_time(L, t, step);
                time_arr[i + 1][L] = t + dt;
                par[i + 1][L] = L;
            }
        }
    }

    int best_lane = 0;
    for(int L = 1; L < n; L++) {
        if(time_arr[M][L] < time_arr[M][best_lane]) {
            best_lane = L;
        }
    }

    vector<int> lane_seq{best_lane};
    vector<double> switch_times;
    int cur_l = best_lane, cur_i = M;
    while(true) {
        int p = par[cur_i][cur_l];
        if(p == -1) {
            break;
        }
        if(p == cur_l) {
            cur_i--;
        } else {
            switch_times.push_back(time_arr[cur_i][p]);
            cur_l = p;
            lane_seq.push_back(cur_l);
        }
    }

    reverse(lane_seq.begin(), lane_seq.end());
    reverse(switch_times.begin(), switch_times.end());

    vector<double> dp_times = switch_times;
    for(size_t i = 0; i < switch_times.size(); i++) {
        int prev = lane_seq[i], next = lane_seq[i + 1];
        double c_dur = c_change * abs(next - prev), a_p = a_arr[prev],
               b_p = b_arr[prev], d_p = delta_arr[prev], a_n = a_arr[next],
               b_n = b_arr[next], d_n = delta_arr[next], t_dp = switch_times[i],
               t = t_dp;
        for(int it = 0; it < 60; it++) {
            double f = (b_p + a_p * sin(t + d_p)) -
                       (b_n + a_n * sin(t + c_dur + d_n)),
                   fp = a_p * cos(t + d_p) - a_n * cos(t + c_dur + d_n);
            if(fabs(fp) < 1e-13) {
                break;
            }

            double step_t = max(-0.3, min(0.3, f / fp));
            t -= step_t;
            if(fabs(step_t) < 1e-16) {
                break;
            }
        }

        if(a_p * cos(t + d_p) - a_n * cos(t + c_dur + d_n) >= 0) {
            t = t_dp;
        }

        double min_t = (i == 0)
                           ? 0.0
                           : switch_times[i - 1] +
                                 c_change * abs(lane_seq[i] - lane_seq[i - 1]);
        switch_times[i] = max(t, min_t);
    }

    auto compute = [&](const vector<double>& times) {
        double total_dist = 0, cur_time = 0;
        size_t len = times.size();
        for(size_t i = 0; i < times.size(); i++) {
            int prev = lane_seq[i], next = lane_seq[i + 1];
            double t_sw = times[i], a = a_arr[prev], b = b_arr[prev],
                   d = delta_arr[prev],
                   seg = b * (t_sw - cur_time) -
                         a * (cos(t_sw + d) - cos(cur_time + d));
            if(total_dist + seg >= dist_total) {
                len = i;
                break;
            }
            total_dist += seg;
            cur_time = t_sw + c_change * abs(next - prev);
        }

        double rem = max(0.0, dist_total - total_dist);
        double t = cur_time + drive_time_exact(lane_seq[len], cur_time, rem);
        return make_pair(t, len);
    };

    auto [t_refined, len_refined] = compute(switch_times);
    auto [t_dp, len_dp] = compute(dp_times);

    const vector<double>& chosen = (t_dp < t_refined) ? dp_times : switch_times;
    double t_end = min(t_refined, t_dp);
    size_t schedule_len = (t_dp < t_refined) ? len_dp : len_refined;

    cout << fixed << setprecision(17);
    cout << t_end << "\n";
    cout << schedule_len << "\n";
    for(size_t i = 0; i < schedule_len; i++) {
        cout << (lane_seq[i + 1] + 1) << " " << chosen[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
import sys
import math
from array import array


def solve() -> None:
    # Read all input tokens.
    data = sys.stdin.read().strip().split()

    # Empty input guard.
    if not data:
        return

    # Parse first line.
    n = int(data[0])
    dist_total = float(data[1])
    c_change = float(data[2])

    # Arrays for lane parameters.
    a_arr = [0.0] * n
    b_arr = [0.0] * n
    delta_arr = [0.0] * n

    # Parse lane descriptions.
    ptr = 3
    for i in range(n):
        a_arr[i] = float(data[ptr])
        b_arr[i] = float(data[ptr + 1])
        delta_arr[i] = float(data[ptr + 2])
        ptr += 3

    # Number of distance grid steps.
    M = 200000

    # Size of one distance step.
    step_dist = dist_total / M

    # Flat indexing helper for DP arrays.
    #
    # State (i, lane) is stored at:
    #     index = i * n + lane
    def idx(i: int, lane: int) -> int:
        return i * n + lane

    # Exact driving-time solver using bisection.
    #
    # It solves:
    #   b * dt - a * (cos(t_start + dt + delta)
    #                 - cos(t_start + delta)) = dx
    def drive_time_exact(lane: int, t_start: float, dx: float) -> float:
        # No distance means no driving time.
        if dx <= 0.0:
            return 0.0

        # Lane parameters.
        a = a_arr[lane]
        b = b_arr[lane]
        d = delta_arr[lane]

        # Cosine at starting phase.
        cos_t0 = math.cos(t_start + d)

        # Lower bound: pretend speed is maximum b + a.
        lo = dx / (b + a)

        # Upper bound: pretend speed is minimum b - a.
        # Since b > a, this is positive.
        hi = dx / (b - a) if a > 0.0 else lo

        # Safety.
        if hi < lo:
            hi = lo

        # Bisection. 100 iterations is enough for double precision.
        for _ in range(100):
            mid = 0.5 * (lo + hi)

            # Traveled distance with time mid minus requested dx.
            f = b * mid - a * (math.cos(t_start + mid + d) - cos_t0) - dx

            # Too much distance: time is too large.
            if f > 0.0:
                hi = mid
            else:
                lo = mid

        # Return midpoint.
        return 0.5 * (lo + hi)

    # Fast Newton solver for one tiny grid distance.
    def drive_time(lane: int, t_start: float, dx: float) -> float:
        # Lane parameters.
        a = a_arr[lane]
        b = b_arr[lane]
        d = delta_arr[lane]

        # Starting phase sin/cos.
        phase = t_start + d
        cos_t = math.cos(phase)
        sin_t = math.sin(phase)

        # Initial estimate using instantaneous speed.
        dt = dx / (b + a * sin_t)

        # Four Newton iterations.
        for _ in range(4):
            dt2 = dt * dt

            # Taylor approximation of cos(dt).
            cos_dt = (
                1.0
                - dt2
                * 0.5
                * (
                    1.0
                    - dt2
                    / 12.0
                    * (1.0 - dt2 / 30.0 * (1.0 - dt2 / 56.0))
                )
            )

            # Taylor approximation of sin(dt).
            sin_dt = dt * (
                1.0
                - dt2
                / 6.0
                * (
                    1.0
                    - dt2
                    / 20.0
                    * (
                        1.0
                        - dt2
                        / 42.0
                        * (1.0 - dt2 / 72.0)
                    )
                )
            )

            # cos(t_start + dt + delta).
            cos_a = cos_t * cos_dt - sin_t * sin_dt

            # sin(t_start + dt + delta).
            sin_a = sin_t * cos_dt + cos_t * sin_dt

            # Function value: distance(dt) - dx.
            f = b * dt - a * (cos_a - cos_t) - dx

            # Derivative equals final speed.
            fp = b + a * sin_a

            # Newton update.
            dt -= f / fp

        return dt

    # Infinity value for DP.
    INF = 1.0e100

    # Total number of DP states.
    total_states = (M + 1) * n

    # DP time array, stored flat for memory efficiency.
    time_arr = array("d", [INF]) * total_states

    # Parent array:
    #   -1 means start/unset,
    #    same lane means driving parent,
    #    different lane means lane-change parent.
    #
    # Signed char is enough because lane indices are 0..4 and -1 is needed.
    par = array("b", [-1]) * total_states

    # Start state: distance 0, lane 0, time 0.
    time_arr[idx(0, 0)] = 0.0

    # Precompute switch costs.
    switch_cost = [[0.0] * n for _ in range(n)]
    for lane in range(n):
        for prev_lane in range(n):
            switch_cost[lane][prev_lane] = c_change * abs(lane - prev_lane)

    # Main DP.
    for i in range(M + 1):
        base = i * n

        # Snapshot before lane-change relaxation at this distance.
        drive_arrival = [time_arr[base + lane] for lane in range(n)]

        # Try all single lane changes at the same position.
        for lane in range(n):
            best = time_arr[base + lane]
            best_parent = par[base + lane]

            for prev_lane in range(n):
                if prev_lane == lane:
                    continue

                cand = drive_arrival[prev_lane] + switch_cost[lane][prev_lane]

                if cand < best:
                    best = cand
                    best_parent = prev_lane

            time_arr[base + lane] = best
            par[base + lane] = best_parent

        # Drive to the next grid position.
        if i < M:
            next_base = (i + 1) * n

            for lane in range(n):
                t = time_arr[base + lane]
                dt = drive_time(lane, t, step_dist)

                time_arr[next_base + lane] = t + dt
                par[next_base + lane] = lane

    # Choose best final lane.
    best_lane = 0
    final_base = M * n
    for lane in range(1, n):
        if time_arr[final_base + lane] < time_arr[final_base + best_lane]:
            best_lane = lane

    # Reconstruct lane sequence and switch times.
    lane_seq = [best_lane]
    switch_times = []

    cur_i = M
    cur_lane = best_lane

    while True:
        p = par[idx(cur_i, cur_lane)]

        # Reached the start.
        if p == -1:
            break

        if p == cur_lane:
            # Driving step.
            cur_i -= 1
        else:
            # Lane change from p to cur_lane.
            switch_times.append(time_arr[idx(cur_i, p)])

            # Continue reconstruction in parent lane.
            cur_lane = p
            lane_seq.append(cur_lane)

    # Reverse because reconstruction was backwards.
    lane_seq.reverse()
    switch_times.reverse()

    # Store original DP switch times as fallback.
    dp_times = switch_times[:]

    # Refine switch times using local optimality.
    for i in range(len(switch_times)):
        prev_lane = lane_seq[i]
        next_lane = lane_seq[i + 1]

        # Duration of this lane change.
        c_dur = c_change * abs(next_lane - prev_lane)

        # Lane parameters.
        a_p = a_arr[prev_lane]
        b_p = b_arr[prev_lane]
        d_p = delta_arr[prev_lane]

        a_n = a_arr[next_lane]
        b_n = b_arr[next_lane]
        d_n = delta_arr[next_lane]

        # Start from DP estimate.
        t_dp = switch_times[i]
        t = t_dp

        # Newton solve:
        #   v_prev(t) - v_next(t + c_dur) = 0
        for _ in range(60):
            f = (
                b_p
                + a_p * math.sin(t + d_p)
                - b_n
                - a_n * math.sin(t + c_dur + d_n)
            )

            fp = (
                a_p * math.cos(t + d_p)
                - a_n * math.cos(t + c_dur + d_n)
            )

            # Avoid unstable division.
            if abs(fp) < 1e-13:
                break

            # Clamp Newton step.
            step_t = f / fp
            if step_t < -0.3:
                step_t = -0.3
            elif step_t > 0.3:
                step_t = 0.3

            t -= step_t

            if abs(step_t) < 1e-16:
                break

        # Reject suspicious stationary point.
        derivative = (
            a_p * math.cos(t + d_p)
            - a_n * math.cos(t + c_dur + d_n)
        )

        if derivative >= 0.0:
            t = t_dp

        # Ensure chronological feasibility.
        if i == 0:
            min_t = 0.0
        else:
            min_t = (
                switch_times[i - 1]
                + c_change * abs(lane_seq[i] - lane_seq[i - 1])
            )

        switch_times[i] = max(t, min_t)

    # Exact schedule evaluation.
    def compute(times):
        total_dist = 0.0
        cur_time = 0.0

        # By default, all switches are used.
        used_switches = len(times)

        for i, t_sw in enumerate(times):
            prev_lane = lane_seq[i]
            next_lane = lane_seq[i + 1]

            a = a_arr[prev_lane]
            b = b_arr[prev_lane]
            d = delta_arr[prev_lane]

            # Distance driven before this switch.
            seg = (
                b * (t_sw - cur_time)
                - a * (math.cos(t_sw + d) - math.cos(cur_time + d))
            )

            # If target is reached before this switch, stop here.
            if total_dist + seg >= dist_total:
                used_switches = i
                break

            total_dist += seg

            # Add switch duration.
            cur_time = t_sw + c_change * abs(next_lane - prev_lane)

        # Remaining distance to finish.
        rem = max(0.0, dist_total - total_dist)

        # Current lane is lane_seq[used_switches].
        finish_lane = lane_seq[used_switches]

        # Drive remaining distance exactly.
        t_end = cur_time + drive_time_exact(finish_lane, cur_time, rem)

        return t_end, used_switches

    # Compare refined and unrefined schedules.
    t_refined, len_refined = compute(switch_times)
    t_dp, len_dp = compute(dp_times)

    if t_dp < t_refined:
        chosen_times = dp_times
        t_end = t_dp
        schedule_len = len_dp
    else:
        chosen_times = switch_times
        t_end = t_refined
        schedule_len = len_refined

    # Output result.
    out = []
    out.append(f"{t_end:.17f}")
    out.append(str(schedule_len))

    for i in range(schedule_len):
        # Convert lane index to 1-based.
        out.append(f"{lane_seq[i + 1] + 1} {chosen_times[i]:.17f}")

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()
```

---

## 5. Compressed Editorial

Use the exact integral

\[
\text{dist}=b\Delta t-a(\cos(t+\Delta t+\delta)-\cos(t+\delta)).
\]

Discretize distance into `M = 200000` steps. Let `dp[i][lane]` be the earliest time to reach distance `i*d/M` in that lane. At each grid point, relax all lane changes with cost `c*abs(x-y)`, then drive one grid step in the same lane by solving the integral equation with Newton's method.

Store parents to reconstruct the lane sequence and approximate switch times.

Because switches are restricted to grid points, refine every reconstructed switch. For a switch from lane `A` to lane `B` of duration `s`, the local optimality condition is

\[
v_A(t)=v_B(t+s).
\]

Solve this equation by Newton's method near the DP switch time, with clamped steps.

Finally, exactly recompute the schedule distance using the closed-form integral. If the destination is reached before some planned switch, discard later switches. Solve the final partial segment by bisection. Compare refined and original DP schedules and output the better one.
