<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

331. Traffic Jam
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The most annoying thing in Moscow traffic jams is that drivers constantly try to suddenly change lanes in order to move faster. In this problem you'll have to find out whether this is a reasonable strategy or not.

We'll study a relatively simple mathematical model of a traffic jam. Assume that there's an N-lane road, lanes numbered from 1 to N, and ith lane is moving with speed bi+ai·sin(t+δi) at the moment t. It is always true that bi > ai, i.e., the speed of movement is always positive. You can change the lane you're in at any time, it takes c·|x-y| to change from xth lane to yth. We'll assume that you're not moving forward during that period.

Determine the time you need to travel the distance of d, and the method of achieving that time. You're starting at the moment 0 at lane 1, you may finish at any lane.

Input
The first line of input contains two integers N and d and a floating-point number c, 1 ≤ N ≤ 5, 1 ≤ d ≤ 1000, 0.001 ≤ c ≤ 1000. The next N lines describe lanes, each containing two integers ai and bi and a floating-point number δi, 0 ≤ ai < bi ≤ 100, 0 ≤δi < 2π.

Output
On the first line of output print the minimal time required to travel the distance of d. On the second line of output print the number K of lane changes required to do that. K should not be more than 106, it is guaranteed that there always exists an optimal strategy requiring not more than 106 lane changes. On the next K lines print the changes themselves, each line should contain the new lane number and the time when the change is started. The changes should be printed in chronological order. If there're many possible schedules, output any.

Output all the floating-point numbers with maximal precision possible. Your solution will be considered correct if verifying your schedule doesn't lead to discrepancies of more than 10-6 (in checking the total distance traveled, in checking that lane changes are non-overlapping, etc), so it's better for you to output at least 10-12 digits after the decimal point in each floating-point number.

Example(s)
sample input
sample output
1 100 0.5
4 5 0
19.71726232777025
0

sample input
sample output
3 100 0.5
4 5 0
2 5 0.5
0 5 0
19.052103083697858
4
2 3.6645304897691258
1 5.783185307179586
2 9.947715796948712
3 15.207963267948966

<|response|>
## 1. Abridged problem statement

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

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

and `b_i > a_i`, so speed is always positive.

You start at time `0` in lane `1`, at distance `0`, and need to travel distance `d`. You may change from lane `x` to lane `y`; this takes

\[
c\cdot |x-y|
\]

time, during which you do not move forward.

Find the minimum finishing time and output one lane-change schedule achieving it.

---

## 2. Key observations needed to solve the problem

### Observation 1: Distance in one lane can be integrated exactly

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
\]

which equals

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

Since speed is always positive, this function is strictly increasing in `Δt`. Therefore, for a given distance, the required driving time is uniquely determined and can be found by Newton iteration or bisection.

---

### Observation 2: Discretize distance, not time

The speeds are continuous and periodic, and lane changes can happen at arbitrary times. Instead of discretizing time, we discretize distance:

```text
M = 200000
step = d / M
```

Let

```text
dp[i][lane]
```

be the earliest time when we can reach distance `i * step` and be in `lane`.

---

### Observation 3: Two transition types

At each distance grid point:

1. **Change lane without moving forward**

   From lane `x` to lane `y`:

   \[
   dp[i][y] = \min(dp[i][y], dp[i][x] + c|x-y|)
   \]

2. **Drive one distance step**

   From `(i, lane)` to `(i + 1, lane)`.

   The required time is obtained by solving the integral equation for distance `step`.

---

### Observation 4: Reconstructing the path gives approximate switch times

The DP only allows switching at grid positions. The true optimum may switch between grid points.

Therefore, after reconstructing the lane sequence, we locally refine each switch time.

---

### Observation 5: Optimal switch condition

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

\[
s=c|A-B|.
\]

If the switch starts at time `t`, then we enter lane `B` at time `t+s`.

At a local optimum, shifting this switch slightly should not improve the answer. This gives:

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

or

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

We solve this equation by Newton iteration near the DP switch time.

---

## 3. Full solution approach based on the observations

### Step 1: Precompute DP over distance grid

Use `M = 200000`.

```text
dp[i][lane] = minimum time to reach distance i * d / M in this lane
```

Initial state:

```text
dp[0][0] = 0
```

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

For every grid position `i`:

1. Relax all lane changes at this fixed distance.
2. For every lane, drive one distance step to `i + 1`.

The driving time for a small distance step is found by Newton iteration using the exact integral. Since `step ≤ 0.005`, the original solution uses Taylor approximations for `sin(dt)` and `cos(dt)` to make the inner loop fast.

---

### Step 2: Store parents

For every state `(i, lane)`, store how it was reached:

- `-1`: starting state,
- same lane: reached by driving from `i - 1`,
- different lane: reached by a lane change at the same distance.

After the DP, choose the best final lane at distance `d`, then follow parents backward to obtain:

- the sequence of lanes,
- approximate lane-change start times.

---

### Step 3: Refine lane-change times

For each switch from lane `A` to lane `B`, with switching duration `s`, solve:

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

That is:

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

Newton derivative:

\[
a_A\cos(t+\delta_A)-a_B\cos(t+s+\delta_B).
\]

We clamp Newton steps to avoid jumping to a wrong periodic root.

Also, after refinement, ensure lane changes remain chronological and non-overlapping.

---

### Step 4: Exact final simulation

Given the reconstructed schedule, recompute the actually traveled distance exactly using the closed-form integral.

If the destination is reached before some planned switch, discard that switch and all later switches.

For the final partial segment, solve the integral equation exactly by bisection.

As a safety measure, evaluate both:

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

and output the better one.

---

## 4. 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;
}
```

---

## 5. Python Solution

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


def solve() -> None:
    data = sys.stdin.read().strip().split()

    if not data:
        return

    n = int(data[0])
    dist_total = float(data[1])
    c_change = float(data[2])

    a_arr = [0.0] * n
    b_arr = [0.0] * n
    delta_arr = [0.0] * n

    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

    M = 200000
    step_dist = dist_total / M

    def idx(i: int, lane: int) -> int:
        return i * n + lane

    def drive_time_exact(lane: int, t_start: float, dx: float) -> float:
        if dx <= 0.0:
            return 0.0

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

        cos_t0 = math.cos(t_start + d)

        lo = dx / (b + a)
        hi = dx / (b - a) if a > 0.0 else lo

        if hi < lo:
            hi = lo

        for _ in range(100):
            mid = 0.5 * (lo + hi)
            f = b * mid - a * (math.cos(t_start + mid + d) - cos_t0) - dx

            if f > 0.0:
                hi = mid
            else:
                lo = mid

        return 0.5 * (lo + hi)

    def drive_time(lane: int, t_start: float, dx: float) -> float:
        a = a_arr[lane]
        b = b_arr[lane]
        d = delta_arr[lane]

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

        dt = dx / (b + a * sin_t)

        for _ in range(4):
            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

    INF = 1.0e100

    total_states = (M + 1) * n

    time_arr = array("d", [INF]) * total_states
    par = array("b", [-1]) * total_states

    time_arr[idx(0, 0)] = 0.0

    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)

    for i in range(M + 1):
        base = i * n

        drive_arrival = [time_arr[base + lane] for lane in range(n)]

        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

        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

    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

    lane_seq = [best_lane]
    switch_times = []

    cur_i = M
    cur_lane = best_lane

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

        if p == -1:
            break

        if p == cur_lane:
            cur_i -= 1
        else:
            switch_times.append(time_arr[idx(cur_i, p)])
            cur_lane = p
            lane_seq.append(cur_lane)

    lane_seq.reverse()
    switch_times.reverse()

    dp_times = switch_times[:]

    for i in range(len(switch_times)):
        prev_lane = lane_seq[i]
        next_lane = lane_seq[i + 1]

        c_dur = c_change * abs(next_lane - prev_lane)

        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]

        t_dp = switch_times[i]
        t = t_dp

        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)
            )

            if abs(fp) < 1e-13:
                break

            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

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

        if derivative >= 0.0:
            t = t_dp

        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)

    def compute(times):
        total_dist = 0.0
        cur_time = 0.0

        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]

            seg = (
                b * (t_sw - cur_time)
                - a * (math.cos(t_sw + d) - math.cos(cur_time + d))
            )

            if total_dist + seg >= dist_total:
                used_switches = i
                break

            total_dist += seg

            cur_time = t_sw + c_change * abs(next_lane - prev_lane)

        rem = max(0.0, dist_total - total_dist)

        finish_lane = lane_seq[used_switches]

        t_end = cur_time + drive_time_exact(finish_lane, cur_time, rem)

        return t_end, used_switches

    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

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

    for i in range(schedule_len):
        out.append(f"{lane_seq[i + 1] + 1} {chosen_times[i]:.17f}")

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


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