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

There are N adjacent rivers 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) + (river current (0, v_i)).

Choose how long t_i to spend in each river to maximize the straight-line distance from the start when he reaches the far right bank. Output -1 if impossible, otherwise the maximum distance and optimal times t_1, ..., t_N.

---

## 2. Key observations

1. **East displacement is fixed.** Total east movement must be W = sum w_i. Maximizing final distance sqrt(W^2 + Y^2) is equivalent to maximizing total north displacement Y.

2. **Constant direction per river.** For fixed crossing time t_i, changing direction mid-river cannot improve displacement (convexity/averaging), so one constant swim direction per river is optimal.

3. **Crossing constraint.** East swim component is w_i/t_i, and it must be at most u, so t_i >= w_i/u. Feasibility: sum(w_i/u) <= T; otherwise -1.

4. **Given t_i, best north contribution** is g_i(t_i) = v_i*t_i + sqrt((u*t_i)^2 - w_i^2). Extra time always increases g_i, so we use all T seconds.

5. **Concave optimization.** Each g_i is concave, so KKT applies: at optimum, there exists lambda such that g_i'(t_i) = lambda for all i, where g_i'(t) = v_i + (u^2 * t) / sqrt((u*t)^2 - w_i^2).

6. **Closed-form t_i(lambda).** Setting a = lambda - v_i and solving: t_i(lambda) = w_i*a / (u*sqrt(a^2 - u^2)), valid for a > u (i.e. lambda > v_i + u). Sum t_i(lambda) is monotonically decreasing in lambda, so binary search lambda to satisfy sum t_i = T.

---

## 3. Full solution approach

1. Check feasibility: if sum(w_i/u) > T, output -1.
2. Binary search lambda in (max_i(v_i + u), infinity): compute t_i(lambda) for each i, sum them. If sum > T increase lambda, else decrease. 200 iterations suffice for 1e-12 precision.
3. With the found lambda, compute times t_i, W = sum w_i, Y = sum g_i(t_i).
4. Output sqrt(W^2 + Y^2) and the times.

Complexity: O(N * 200) = O(N), trivial for N <= 50.

---

## 4. C++ implementation

```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 u, T;
vector<double> w, v;

void read() {
    cin >> N >> u >> T;
    w.resize(N);
    v.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
}

void solve() {
    // We can think of this as an optimization problem. Let t[1], ..., t[n] be
    // the times we spend at each river. Clearly T = t[1] + ... + t[n], because
    // there is no point in wasting time waiting. Also, we know the smallest
    // amount of time t[i] >= w[i] / u. For a given t[i], we can always show
    // that it's optimal to swim in a constant direction vector (x[i], y[i])
    // with a fairly simple convexity argument (if we change directions at some
    // point, we can consider the average between the two vectors for the same
    // amount of time). The constraint is that u^2 = x[i]^2 + (y[i] + v[i])^2.
    //
    // For fixed t[i] we must have x[i] = w[i] / t[i] (exact crossing). To
    // maximize total northward displacement we take the root:
    //
    //     y[i] = -v[i] + sqrt(u^2 - x[i]^2)
    //
    // The total eastward displacement W = sum w[i] is fixed. The total
    // northward displacement becomes:
    //
    //     Y = sum g_i(t[i])
    //       = sum y[i]*t[i]
    //       = sum v[i]*t[i] + sum sqrt((u*t[i])^2 - w[i]^2).
    //
    // We therefore need to choose t[1]..t[n] (t[i] >= w[i]/u, sum t[i] = t)
    // that maximize Y. The final answer distance is sqrt(W*W + Y*Y). If sum
    // (w[i]/u) > t it is impossible (-1). Otherwise the optimum always uses
    // exactly t seconds (extra time always gives extra drift).
    //
    // To optimize this, we can do a gradient descent like approach, but we can
    // also do Lagrange multipliers. Being more precise, the equality constraint
    // is a single one in T = t[1] + ... + t[n], so the partial derivative of
    // this is 1 for each t[i]. However, we have the inequality constraints t[i]
    // >= w[i] / u for which we also need a Lagrange multiplier, which we denote
    // my \mu_i. By KKT, we simply know that g_i'(t) = \lambda - \mu_i. However,
    // g_i(t) is concave, or g_i'(t) is strictly decreasing and t -> w[i]/u
    // has g_i'(t) -> +inf, meaning the optimum we always has t[i] > w[i]/u
    // because g_i'(t) is undefined before w[i]/u. In other words, any t[:] \in
    // R^n we find will have t[i] > w[i]/u simply because the g_i'(t) term
    // requires this. This means that \mu_i will be inactive and we can set
    // \mu_i = 0. Therefore, all g_i'(t) = \lambda for the same \lambda. The
    // derivative is:
    //
    //     g_i'(t) = v[i] + (u*u*t) / sqrt((u*t)^2 - w[i]*w[i])
    //
    // For a candidate \lambda we solve for each t[i] in closed form:
    //
    //     a = \lambda - v[i]
    //     t[i] = w[i] * a / (u * sqrt(a*a - u*u))     (valid when a > u)
    //
    // We binary-search \lambda (approx 100-200 iterations suffice for 1e-12
    // precision) until sum t[i] equals the given t (larger \lambda makes every
    // t[i] smaller). This gives us both the optimal Y and the t[1], ..., t[n]
    // (and so answer to the problem). It works in O(N log eps^-1), ignoring the
    // complexity of explicitly solving the t[i] that requires computing a
    // square root.

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

    double max_asympt = 0.0;
    for(int i = 0; i < N; i++) {
        max_asympt = max(max_asympt, v[i] + u);
    }

    auto compute_times = [&](double lam) -> vector<double> {
        vector<double> res(N);
        for(int i = 0; i < N; i++) {
            double a = lam - v[i];
            double sqrt_term = sqrt(a * a - u * u);
            res[i] = w[i] * a / (u * sqrt_term);
        }
        return res;
    };

    double low = max_asympt + 1e-9;
    double high = 1e18;
    for(int iter = 0; iter < 200; iter++) {
        double mid = (low + high) / 2.0;
        auto ts = compute_times(mid);
        double sumt = 0.0;
        for(double t: ts) {
            sumt += t;
        }
        if(sumt > T) {
            low = mid;
        } else {
            high = mid;
        }
    }

    double lambda_val = (low + high) / 2.0;
    auto times = compute_times(lambda_val);

    double Y = 0.0;
    double W = 0.0;
    for(int i = 0; i < N; i++) {
        W += w[i];
        double ti = times[i];
        Y += v[i] * ti + sqrt(u * ti * ti * u - w[i] * w[i]);
    }
    double dist = sqrt(W * W + Y * Y);

    cout << fixed << setprecision(10) << dist << endl;
    cout << fixed << setprecision(10);
    for(int i = 0; i < N; i++) {
        if(i > 0) {
            cout << ' ';
        }
        cout << times[i];
    }
    cout << 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();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation (detailed comments)

```python
import math
import sys

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

    # Minimal time to cross all rivers: each river i needs at least w_i/u seconds,
    # because your east component in still water cannot exceed u.
    min_time = sum(wi / u for wi in w)
    if min_time > T + 1e-12:
        print(-1)
        return

    # Lambda must satisfy lambda > v_i + u for all i, otherwise t_i(lambda) is undefined.
    max_asympt = max(vi + u for vi in v)

    # Compute the vector of times t_i given lambda using the derived closed-form:
    # a = lambda - v_i
    # t_i = w_i * a / (u * sqrt(a^2 - u^2))
    def compute_times(lam: float):
        res = [0.0] * N
        uu = u * u
        for i in range(N):
            a = lam - v[i]
            # a must be > u, ensured by our binary search lower bound
            sqrt_term = math.sqrt(a * a - uu)
            res[i] = w[i] * a / (u * sqrt_term)
        return res

    # Binary search lambda so that sum t_i == T.
    low = max_asympt + 1e-9
    high = 1e18

    for _ in range(200):
        mid = (low + high) / 2.0
        ts = compute_times(mid)
        sumt = sum(ts)

        # sumt decreases as lambda increases.
        if sumt > T:
            low = mid
        else:
            high = mid

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

    # Compute W (total east) and Y (total north), then distance.
    W = sum(w)
    Y = 0.0
    for i in range(N):
        ti = times[i]
        # north displacement in river i:
        # v_i * t_i + sqrt((u*t_i)^2 - w_i^2)
        Y += v[i] * ti + math.sqrt((u * ti) * (u * ti) - w[i] * w[i])

    dist = math.hypot(W, Y)  # sqrt(W^2 + Y^2)

    # Output formatting
    print(f"{dist:.10f}")
    print(" ".join(f"{ti:.10f}" for ti in times))

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