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

401. Geologist Dubrovsky
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

Geologist Dubrovsky travels a lot around the world and often faces different unusual phenomena. And now he found a unique place on the planet, where N rivers flow in parallel tight next to each other. The distance between each pair of neighbouring rivers can be neglected. Rivers flow from the south to the north. Geologist stays on the left bank of the most western river and wants to get to the right bank of the most eastern river. The flow speed of i-th river is vi meters per second and its width is wi meters. Geologist Dubrovsky swims with the speed u meters per second in still water. If he swims across river, his real speed is a vector sum of his own speed vector and the speed vector of the river flow. What is the maximal distance Dubrovsky can get from his original position by the time of sunset, if he has only t seconds left? Remember that his destination point is a point on the right bank of the easternmost river.
Input
The first line of the input contains three integer numbers N, u and t (1 ≤ N ≤ 50; 1 ≤ u,t ≤ 1000). Each of the following N lines contains a pair of integers wi, vi (1 ≤ wi, vi ≤ 1000) describing corresponding parameters of the i-th river.
Output
To the first line of the output write the desired distance or -1 if geologist can't reach the right bank of the most eastern river in t seconds. The distance with a relative or absolute error of at most 10-6 will be considered correct. If solution exists the second line of the output should contain the sequence t1, t2,..., tN, where ti is the time spent crossing the river i in the case of optimal track. The track is optimal if as a result Dubrovsky gets to the point on the right bank of the easternmost river, which is the farthest from his original position.
Example(s)
sample input
sample output
1 1 1
1 1
1.4142135624
1.0000000000

sample input
sample output
2 1 6
1 1
2 1

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

There are **N** adjacent rivers (no gaps), flowing **north** with speeds \(v_i\) and widths \(w_i\).  
A geologist starts at the **left bank** of the westernmost river and must end at the **right bank** of the easternmost river within **total time \(T\)**.  

He swims at speed **\(u\)** relative to water; his ground velocity equals **(his swim vector) + (current vector \((0,v_i)\))**.

Choose how long \(t_i\) to spend in each river (and implicitly the swimming direction there) to **maximize the distance from the start** when he reaches the far right bank, or output **-1** if it’s impossible to reach in time.

Also output one optimal sequence \(t_1,\dots,t_N\).

---

## 2) Key observations

1. **East displacement is fixed.**  
   To reach the right bank of the last river, total east movement must be
   \[
   W = \sum_{i=1}^N w_i
   \]
   regardless of path. Therefore maximizing final distance
   \(\sqrt{W^2 + Y^2}\) is equivalent to maximizing **total north displacement \(Y\)**.

2. **Per river, constant direction is optimal for fixed time \(t_i\).**  
   If you change direction mid-river, the average of your velocity vectors achieves at least the same displacement (convexity/averaging). So assume **one constant swim direction per river**.

3. **Crossing constraint gives a lower bound on time.**  
   In river \(i\), current has no east component, so east ground speed equals your east swim component:
   \[
   s_{x,i} = \frac{w_i}{t_i}
   \]
   and \(|s_{x,i}| \le u\). Thus:
   \[
   t_i \ge \frac{w_i}{u}.
   \]
   Feasibility requires:
   \[
   \sum_{i=1}^N \frac{w_i}{u} \le T.
   \]
   If not, answer is **-1**.

4. **Given time \(t_i\), best north component is maximal possible.**  
   With fixed \(s_{x,i} = w_i/t_i\), the maximum \(s_{y,i}\) is
   \[
   s_{y,i} = \sqrt{u^2 - \left(\frac{w_i}{t_i}\right)^2}.
   \]
   North ground speed is \(s_{y,i} + v_i\).

5. **Reduced optimization over times only.**  
   The north displacement contributed by river \(i\) becomes:
   \[
   g_i(t) = v_i t + \sqrt{(ut)^2 - w_i^2}, \quad t \ge \frac{w_i}{u}.
   \]
   We maximize \(\sum g_i(t_i)\) subject to \(\sum t_i = T\).

6. **KKT/Lagrange multiplier gives a single parameter \(\lambda\).**  
   For \(t > w_i/u\), \(g_i\) is concave and \(g_i'(t)\) strictly decreases:
   \[
   g_i'(t)= v_i + \frac{u^2 t}{\sqrt{(ut)^2 - w_i^2}}.
   \]
   At optimum, there exists \(\lambda\) such that for all rivers:
   \[
   g_i'(t_i) = \lambda.
   \]

7. **Closed form for \(t_i(\lambda)\) and monotonicity → binary search.**  
   Solving \(g_i'(t)=\lambda\) yields:
   \[
   t_i(\lambda) =
   \frac{w_i(\lambda - v_i)}{u\sqrt{(\lambda - v_i)^2 - u^2}},
   \quad \text{requires } \lambda > v_i + u.
   \]
   The sum \(\sum t_i(\lambda)\) is **monotonically decreasing** in \(\lambda\), so we binary search \(\lambda\) to make \(\sum t_i = T\).

---

## 3) Full solution approach

1. **Read input** \(N, u, T\), and arrays \(w_i, v_i\).
2. **Feasibility check**:
   - Compute \(T_{\min} = \sum w_i/u\).
   - If \(T_{\min} > T\) (with small epsilon), print `-1`.
3. **Binary search \(\lambda\)**:
   - Lower bound: just above \(\max_i(v_i + u)\) so square roots are valid.
   - Upper bound: a large number (e.g. \(10^{18}\)).
   - For a candidate \(\lambda\), compute all \(t_i(\lambda)\) by the closed form, sum them.
   - If sum \(> T\), \(\lambda\) is too small (times too large) ⇒ increase \(\lambda\).
     Else decrease \(\lambda\).
4. After convergence, take the resulting \(t_i\).
5. Compute:
   - \(W=\sum w_i\)
   - \(Y = \sum \left(v_i t_i + \sqrt{(u t_i)^2 - w_i^2}\right)\)
   - Answer distance \(D=\sqrt{W^2 + Y^2}\).
6. Output \(D\) and the times \(t_1,\dots,t_N\).

Complexity: \(O(N \cdot I)\) with \(I\approx 200\) iterations; \(N\le 50\) is trivial.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Geologist Dubrovsky (p401)

  We reduce the problem to choosing times t_i for each river, with constraints:
    - t_i >= w_i / u
    - sum t_i = T
  and we maximize total north displacement:
    Y = sum (v_i * t_i + sqrt((u*t_i)^2 - w_i^2))

  Using KKT, at optimum:
    g_i'(t_i) = lambda  (same lambda for all i)
  where:
    g_i'(t) = v_i + (u^2 * t) / sqrt((u*t)^2 - w_i^2)

  Solving g_i'(t)=lambda gives:
    t_i(lambda) = w_i * (lambda - v_i) / (u * sqrt((lambda - v_i)^2 - u^2))
  valid for lambda > v_i + u.

  Then sum t_i(lambda) decreases as lambda increases -> binary search lambda so sum = T.
*/

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

    int N;
    double u, T;
    cin >> N >> u >> T;

    vector<double> w(N), v(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }

    // 1) Feasibility: minimal time if swimming purely east with speed u in every river
    double min_time = 0.0;
    for (int i = 0; i < N; i++) min_time += w[i] / u;

    if (min_time > T + 1e-12) {
        cout << -1 << "\n";
        return 0;
    }

    // 2) Lambda must satisfy lambda > max_i(v_i + u)
    double low = 0.0;
    for (int i = 0; i < N; i++) low = max(low, v[i] + u);
    low += 1e-9;          // ensure strictly greater (avoid sqrt of 0)

    double high = 1e18;   // big enough upper bound

    auto compute_times = [&](double lambda) {
        vector<double> t(N);
        double uu = u * u;
        for (int i = 0; i < N; i++) {
            double a = lambda - v[i];             // a > u must hold
            double denom = u * sqrt(a * a - uu);  // u*sqrt(a^2 - u^2)
            t[i] = w[i] * a / denom;
        }
        return t;
    };

    // 3) Binary search lambda so that sum t_i(lambda) = T
    for (int it = 0; it < 200; it++) { // 200 iterations is plenty for 1e-9+ accuracy
        double mid = (low + high) / 2.0;
        auto t = compute_times(mid);

        double sumt = 0.0;
        for (double x : t) sumt += x;

        // sumt decreases with lambda
        if (sumt > T) low = mid;   // need smaller times -> increase lambda
        else high = mid;
    }

    double lambda = (low + high) / 2.0;
    vector<double> t = compute_times(lambda);

    // 4) Compute final distance
    double W = 0.0, Y = 0.0;
    for (int i = 0; i < N; i++) {
        W += w[i];
        double ti = t[i];
        // north displacement in river i:
        // v_i * t_i + sqrt((u*t_i)^2 - w_i^2)
        Y += v[i] * ti + sqrt((u * ti) * (u * ti) - w[i] * w[i]);
    }

    double dist = sqrt(W * W + Y * Y);

    cout << fixed << setprecision(10) << dist << "\n";
    cout << fixed << setprecision(10);
    for (int i = 0; i < N; i++) {
        if (i) cout << ' ';
        cout << t[i];
    }
    cout << "\n";

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
import math

"""
Geologist Dubrovsky (p401)

We maximize final distance from start after crossing all rivers.
Total east displacement W = sum w_i is fixed, so maximize north displacement:

  g_i(t) = v_i * t + sqrt((u*t)^2 - w_i^2),  t >= w_i/u

Concave optimization with constraint sum t_i = T.
KKT => for optimum there exists lambda such that g_i'(t_i) = lambda:

  g_i'(t) = v_i + (u^2 * t) / sqrt((u*t)^2 - w_i^2)

Solve g_i'(t) = lambda in closed form:
  t_i(lambda) = w_i * (lambda - v_i) / (u * sqrt((lambda - v_i)^2 - u^2))
Requires lambda > v_i + u.

Sum t_i(lambda) decreases with lambda -> binary search lambda so sum == T.
"""

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)

    N = int(next(it))
    u = float(next(it))
    T = float(next(it))

    w = [0.0] * N
    v = [0.0] * N
    for i in range(N):
        w[i] = float(next(it))
        v[i] = float(next(it))

    # Feasibility: minimal time is sum w_i/u
    min_time = sum(wi / u for wi in w)
    if min_time > T + 1e-12:
        print(-1)
        return

    # Lower bound for lambda: > max(v_i + u)
    low = max(vi + u for vi in v) + 1e-9
    high = 1e18

    uu = u * u

    def compute_times(lam: float):
        """Return t_i(lam) for all i."""
        ts = [0.0] * N
        for i in range(N):
            a = lam - v[i]                 # must be > u
            ts[i] = w[i] * a / (u * math.sqrt(a * a - uu))
        return ts

    # Binary search lambda
    for _ in range(200):
        mid = (low + high) / 2.0
        ts = compute_times(mid)
        s = sum(ts)
        # s decreases as lambda increases
        if s > T:
            low = mid
        else:
            high = mid

    lam = (low + high) / 2.0
    ts = compute_times(lam)

    # Compute final distance
    W = sum(w)
    Y = 0.0
    for i in range(N):
        ti = ts[i]
        Y += v[i] * ti + math.sqrt((u * ti) * (u * ti) - w[i] * w[i])

    dist = math.hypot(W, Y)

    print(f"{dist:.10f}")
    print(" ".join(f"{ti:.10f}" for ti in ts))


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

These implementations match the editorial approach: feasibility check, KKT-derived closed-form \(t_i(\lambda)\), binary search on \(\lambda\), then compute the maximal distance and output the optimal per-river times.