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

317. Fast Ride
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Is there a Russian who does not like a fast ride?! Royal messenger should get from point A to point B as quickly as possible. Point A has coordinate 0 on the Ox axis. Point B has positive coordinate B on the Ox axis. Of course, the messenger will use horses to get to the destination point. The messenger is not allowed to travel by foot because of an importance of his mission and security reasons.

There are N stables on the straight line from A to B. The i-th stable has Mi horses inside. Each horse is characterized by its speed vj and maximum distance it can gallop dj (after that it falls exhausted). The messenger can change the horse reaching or passing a stable to any horse from that stable without losing time.

Your task is to find the minimum time the messenger needs to get to the point B.

Input
The first line of the input contains two integer numbers B and N (1 ≤ B ≤ 108; 1 ≤ N ≤ 5000), where N is the number of stables. Descriptions of the stables follow. The first line of each description contains two integer numbers Xi, Mi (0 ≤ Xi ≤ 108; 0 < Mi) — the position of the stable and the number of horses in this stable respectively. The following Mi lines contain the description of the horses. Each description of a horse is a pair of integer numbers vj, dj (1 ≤ vj ≤ 108; 1 ≤ dj ≤ 108). The total number of horses in all stables is no more than 105. It is possible that two or more stables have the same position.

Output
Write the minimum time which will take the messenger to get to the point B to the output. The answer should be written with no less than 3 digits after the decimal point. If the solution does not exist, write -1 to the output.

Example(s)
sample input
sample output
10 3
5 2
1 100
10 3
0 1
1 50
8 1
2 3
6.30000000

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

You need to travel along the x-axis from **A = 0** to **B > 0** as fast as possible.

There are **N stables** at positions \(X_i\) (some positions may repeat). In stable \(i\) there are \(M_i\) horses; each horse has:

- speed \(v\)
- maximum running distance \(d\)

You may **instantly** change horses whenever you **reach or pass** a stable. You cannot walk.

Output the **minimum possible time** to reach \(B\), with at least 3 digits after the decimal point, or **-1** if impossible.

Constraints: \(N \le 5000\), total horses \(\le 10^5\), \(B \le 10^8\). Time limit is very small.

---

## 2) Key observations needed to solve the problem

1. **Sort stables by coordinate**  
   Travel is only forward along the line, so we should process stables from left to right.

2. **DP formulation**  
   Let `dp[i]` be the minimum time to reach stable `i` at position \(x_i\).  
   From stable `i`, using a horse \((v, d)\), you can reach any point up to \(x_i + d\), including any stable `j` with:
   \[
   x_j \le x_i + d
   \]
   Transition:
   \[
   dp[j] \le dp[i] + \frac{x_j - x_i}{v}
   \]

3. **Each horse induces a linear function in \(x_j\)**  
   Rewrite:
   \[
   dp[i] + \frac{x_j - x_i}{v}
   = \left(\frac{1}{v}\right) x_j + \left(dp[i] - \frac{x_i}{v}\right)
   \]
   For fixed \((i, v)\), this is a **line** \(y = kx + m\) where:
   - \(k = 1/v\)
   - \(m = dp[i] - x_i/v\)

4. **But each line is valid only on an index range**  
   The horse can only be used until distance \(d\), so it can update only stables with \(x \le x_i + d\).  
   If `r` is the last index reachable, the line applies to indices:
   \[
   [i+1, r]
   \]

5. **We need: range-add line + point query min**  
   - Add a line to a range of indices.
   - Query the minimum value at a single index `i` for \(x = x_i\).

6. **Segment tree of CHT containers**  
   Classic technique:
   - Build a segment tree over stable indices.
   - Each segment tree node stores a convex hull trick (CHT) structure supporting:
     - `addLine(k, m)`
     - `query(x)` → minimum \(kx+m\)
   - Range add: decompose interval into \(O(\log N)\) nodes and add line to each.
   - Point query: traverse root-to-leaf, query all hulls on the path, take minimum.

This makes the solution fast enough for the tight limits.

---

## 3) Full solution approach

### Step A: Preprocessing
1. Read \(B, N\) and all stables with their horses.
2. Sort stables by position \(x\).
3. Remove stables with \(x > B\) (they cannot help).
4. If after sorting, **the first stable is not at position 0**, you cannot start (no walking) → print `-1`.

### Step B: DP + segment tree
Maintain:
- `dp[i]` = min time to reach stable `i` (initialize INF)
- `ans` = min time to reach \(B\) directly (initialize INF)
- Segment tree of CHTs for “lines active for index ranges”.

Process stables in increasing order `i = 0..N-1`:
1. If \(x_i = 0\), then `dp[i] = 0` (you start there).
2. Otherwise, compute:
   - `dp[i] = min(dp[i], segTree.pointQuery(i, x_i))`
3. If `dp[i]` is still INF → skip (unreachable).
4. For every horse \((v, d)\) in stable `i`:
   - Let `reach = x_i + d`.
   - If `reach >= B`: update
     \[
     ans = \min(ans,\ dp[i] + (B-x_i)/v)
     \]
   - Find `r` = last stable index such that \(x_r \le reach\) (binary search).
   - If `r > i`, add the line:
     - \(k = 1/v\)
     - \(m = dp[i] - x_i/v\)
     to the segment tree over index interval `[i+1, r]`.

At the end:
- if `ans` is INF → print `-1`
- else print `ans` with fixed precision (e.g. 8 decimals).

### Complexity
Let total horses be \(H \le 10^5\).
- Each horse: one range update → \(O(\log N)\) segment nodes, each does CHT insertion.
- Each stable: one point query → \(O(\log N)\) segment nodes, each does CHT query.

Works in C++ with optimized structures.

---

## 4) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/dp_optimizations/convex_hull_trick.hpp>

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;
};

template<class T, bool maximum = true>
class ConvexHullTrick {
  public:
    static constexpr T inf = is_integral_v<T> ? numeric_limits<T>::max()
                                              : numeric_limits<T>::infinity();

    T div(T a, T b) {
        if constexpr(is_integral_v<T>) {
            return a / b - ((a ^ b) < 0 && a % b);
        } else {
            return a / b;
        }
    }

    struct Line {
        mutable T k, m, p;
        bool operator<(const Line& o) const { return k < o.k; }
        bool operator<(T x) const { return p < x; }
    };

    multiset<Line, less<>> hull;

    using Iter = typename multiset<Line, less<>>::iterator;

    bool intersect(Iter x, Iter y) {
        if(y == hull.end()) {
            return x->p = inf, 0;
        }
        if(x->k == y->k) {
            x->p = x->m > y->m ? inf : -inf;
        } else {
            x->p = div(y->m - x->m, x->k - y->k);
        }
        return x->p >= y->p;
    }

    void add(T k, T m) {
        if constexpr(!maximum) {
            k = -k;
            m = -m;
        }
        auto z = hull.insert({k, m, 0}), y = z++, x = y;
        while(intersect(y, z)) {
            z = hull.erase(z);
        }
        if(x != hull.begin() && intersect(--x, y)) {
            intersect(x, y = hull.erase(y));
        }
        while((y = x) != hull.begin() && (--x)->p >= y->p) {
            intersect(x, hull.erase(y));
        }
    }

    T query(T x) {
        assert(!hull.empty());
        auto l = *hull.lower_bound(x);
        T res = l.k * x + l.m;
        if constexpr(!maximum) {
            res = -res;
        }
        return res;
    }
};

int64_t B;
int N;

struct Stable {
    int64_t x;
    vector<pair<int64_t, int64_t>> horses;
};

struct SegTree {
    int n;
    vector<ConvexHullTrick<double, false>> tree;

    SegTree() : n(0) {}
    SegTree(int n) : n(n), tree(4 * n) {}

    void update(int ql, int qr, double k, double m, int idx, int lo, int hi) {
        if(ql > hi || qr < lo) {
            return;
        }
        if(ql <= lo && hi <= qr) {
            tree[idx].add(k, m);
            return;
        }

        int mid = (lo + hi) / 2;
        update(ql, qr, k, m, 2 * idx, lo, mid);
        update(ql, qr, k, m, 2 * idx + 1, mid + 1, hi);
    }

    double query(int pos, double x, int idx, int lo, int hi) {
        double res = 1e18;
        if(!tree[idx].hull.empty()) {
            res = tree[idx].query(x);
        }
        if(lo == hi) {
            return res;
        }

        int mid = (lo + hi) / 2;
        if(pos <= mid) {
            return min(res, query(pos, x, 2 * idx, lo, mid));
        } else {
            return min(res, query(pos, x, 2 * idx + 1, mid + 1, hi));
        }
    }
};

vector<Stable> stables;

void read() {
    cin >> B >> N;
    stables.resize(N);
    for(int i = 0; i < N; i++) {
        int m;
        cin >> stables[i].x >> m;
        stables[i].horses.resize(m);
        for(int j = 0; j < m; j++) {
            int64_t v, d;
            cin >> v >> d;
            stables[i].horses[j] = {d, v};
        }
    }
}

void solve() {
    // We should ideally aim for something that is quicker than O(N * M) which
    // can be done with a simple DP but might be a bit too tight to pass. We
    // know that every horse can get us from some Xi to some other Xj and all
    // stables between these (we can do a binary search to find the relevant
    // ranges). Afterwards, if these two are [i;r], we would like to update
    // every j > i in this using DP[j] := min(DP[j], (Xj - Xi) / vk + DP[j]) for
    // horse k that can get us from i to j. Implementing this naively by going
    // through all horses (M) and the O(N) reachable stables, results in O(N *
    // M).
    //
    // To make this quicker, we can notice that the second term in the minimum
    // above is actually a linear function. This should immediately lead us to
    // thinking about convex hull trick. Let us build a segment tree like
    // structure over the N stables, with a convex hull trick container in each
    // node. Then after processing some stable i, we would like to add Mi lines
    // to various ranges [i+1, rk]. We can decompose these ranges recursively
    // into O(log N) intervals, and then add line individually to each of the
    // containers covered. This update ends up being in O(log N * log M). The
    // query is then done whenever we are processing some stable, and is simply
    // going through the nodes from the root until a leaf, which is again the
    // same complexity of O(log N * log M). We have O(M) updates and queries,
    // which overall is quicker than O(N * M).

    sort(stables.begin(), stables.end(), [](const Stable& a, const Stable& b) {
        return a.x < b.x;
    });

    while(!stables.empty() && stables.back().x > B) {
        stables.pop_back();
    }

    N = stables.size();
    if(N == 0 || stables[0].x != 0) {
        cout << -1 << endl;
        return;
    }

    SegTree seg(N);
    vector<double> dp(N, 1e18);
    double ans = 1e18;

    for(int i = 0; i < N; i++) {
        if(stables[i].x == 0) {
            dp[i] = 0;
        }

        if(i > 0) {
            double q = seg.query(i, (double)stables[i].x, 1, 0, N - 1);
            dp[i] = min(dp[i], q);
        }

        if(dp[i] >= 1e18) {
            continue;
        }

        for(auto& [d, v]: stables[i].horses) {
            int64_t reach = stables[i].x + d;
            if(reach >= B) {
                ans = min(ans, dp[i] + (double)(B - stables[i].x) / v);
            }

            int r = (int)(upper_bound(
                              stables.begin(), stables.end(), reach,
                              [](int64_t val, const Stable& s) {
                                  return val < s.x;
                              }
                          ) -
                          stables.begin()) -
                    1;

            if(r > i) {
                double slope = 1.0 / v;
                double intercept = dp[i] - (double)stables[i].x / v;
                seg.update(i + 1, r, slope, intercept, 1, 0, N - 1);
            }
        }
    }

    if(ans >= 1e18) {
        cout << -1 << endl;
    } else {
        cout << fixed << setprecision(8) << ans << endl;
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation with detailed comments

Python is much slower under a 0.25s limit, but here is a clean educational version of the same idea using:

- segment tree over indices
- each node stores a **Li Chao tree** for minimum of lines

This mirrors “range add line / point query”.

```python
import sys
import bisect
from math import inf

# Li Chao Tree for MIN over lines y = kx + m on a discrete x-domain (stable positions).
class LiChaoMin:
    __slots__ = ("xs", "k", "m", "left", "right")

    def __init__(self, xs):
        self.xs = xs
        self.k = None
        self.m = None
        self.left = None
        self.right = None

    @staticmethod
    def f(k, m, x):
        return k * x + m

    def add_line(self, k, m, l=0, r=None):
        if r is None:
            r = len(self.xs) - 1

        # If node empty, store directly
        if self.k is None:
            self.k, self.m = k, m
            return

        mid = (l + r) // 2
        xl, xm, xr = self.xs[l], self.xs[mid], self.xs[r]

        curk, curm = self.k, self.m

        # Ensure current line is better at midpoint
        if self.f(k, m, xm) < self.f(curk, curm, xm):
            self.k, self.m, k, m = k, m, curk, curm
            curk, curm = self.k, self.m

        if l == r:
            return

        # The "worse at mid" line may still win on left or right side
        if self.f(k, m, xl) < self.f(curk, curm, xl):
            if self.left is None:
                self.left = LiChaoMin(self.xs)
            self.left.add_line(k, m, l, mid)
        elif self.f(k, m, xr) < self.f(curk, curm, xr):
            if self.right is None:
                self.right = LiChaoMin(self.xs)
            self.right.add_line(k, m, mid + 1, r)

    def query(self, x, l=0, r=None):
        if r is None:
            r = len(self.xs) - 1

        res = inf
        if self.k is not None:
            res = self.f(self.k, self.m, x)

        if l == r:
            return res

        mid = (l + r) // 2
        if x <= self.xs[mid]:
            return res if self.left is None else min(res, self.left.query(x, l, mid))
        else:
            return res if self.right is None else min(res, self.right.query(x, mid + 1, r))


# Segment tree over indices; each node stores Li Chao.
class SegTree:
    def __init__(self, xs):
        self.n = len(xs)
        self.xs = xs
        self.tree = [None] * (4 * self.n)

    def _ensure(self, idx):
        if self.tree[idx] is None:
            self.tree[idx] = LiChaoMin(self.xs)

    # range add line
    def update(self, ql, qr, k, m, idx=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if qr < lo or hi < ql:
            return
        if ql <= lo and hi <= qr:
            self._ensure(idx)
            self.tree[idx].add_line(k, m)
            return
        mid = (lo + hi) // 2
        self.update(ql, qr, k, m, idx * 2, lo, mid)
        self.update(ql, qr, k, m, idx * 2 + 1, mid + 1, hi)

    # point query at index pos for x-coordinate x
    def query(self, pos, x, idx=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1

        best = inf
        if self.tree[idx] is not None:
            best = self.tree[idx].query(x)

        if lo == hi:
            return best

        mid = (lo + hi) // 2
        if pos <= mid:
            return min(best, self.query(pos, x, idx * 2, lo, mid))
        else:
            return min(best, self.query(pos, x, idx * 2 + 1, mid + 1, hi))


def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)

    B = int(next(it))
    N = int(next(it))

    stables = []
    for _ in range(N):
        x = int(next(it))
        m = int(next(it))
        horses = []
        for __ in range(m):
            v = int(next(it))
            d = int(next(it))
            horses.append((d, v))  # (distance, speed)
        stables.append((x, horses))

    # Sort and discard stables beyond B
    stables.sort(key=lambda t: t[0])
    while stables and stables[-1][0] > B:
        stables.pop()

    if not stables or stables[0][0] != 0:
        print(-1)
        return

    xs = [x for x, _ in stables]
    n = len(stables)

    seg = SegTree(xs)
    dp = [inf] * n
    ans = inf

    for i, (xi, horses) in enumerate(stables):
        # starting stables at x=0 are reachable at time 0
        if xi == 0:
            dp[i] = 0.0

        # compute dp from previously added lines
        if i > 0:
            dp[i] = min(dp[i], seg.query(i, float(xi)))

        if dp[i] == inf:
            continue

        for d, v in horses:
            reach = xi + d

            # direct finish to B
            if reach >= B:
                ans = min(ans, dp[i] + (B - xi) / v)

            # last reachable stable index r
            r = bisect.bisect_right(xs, reach) - 1
            if r > i:
                k = 1.0 / v
                m = dp[i] - xi / v
                seg.update(i + 1, r, k, m)

    if ans == inf:
        print(-1)
    else:
        print(f"{ans:.8f}")


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

If you want, I can also provide:
- a version that merges stables with the same \(x\) (sometimes reduces work),
- floating-point robustness notes,
- or a faster Python variant (still unlikely to pass 0.25s, but improved).