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

114. Telecasting station

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Every city in Berland is situated on Ox axis. The government of the country decided to build new telecasting station. After many experiments Berland scientists came to a conclusion that in any city citizens displeasure is equal to product of citizens amount in it by distance between city and TV-station. Find such point on Ox axis for station so that sum of displeasures of all cities is minimal.


Input

Input begins from line with integer positive number N (0<N<15000) – amount of cities in Berland. Following N pairs (X, P) describes cities (0<X, P<50000), where X is a coordinate of city and P is an amount of citizens. All numbers separated by whitespace(s).


Output

Write the best position for TV-station with accuracy 10-5.


Sample Input

4
1 3
2 1
5 2
6 2
Sample Output

3.00000
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

<|response|>
1. Abridged Problem Statement  
You have N cities on the real line. City i is at coordinate xᵢ and has population pᵢ. You want to choose a point p on the line (where to build a TV‐station) so as to minimize the total displeasure  
  F(p) = Σ₁ⁿ pᵢ·|xᵢ − p|.  
Output any optimal p with absolute error ≤ 10⁻⁵.

2. Key Observations  
• F(p) is convex and piecewise linear in p.  
• The slope of F(p) jumps at each city coordinate xᵢ.  
• For p not equal to any xᵢ, the derivative is  
  F′(p) = (sum of weights to the left of p) − (sum of weights to the right of p).  
• The minimum occurs when F′(p) crosses zero, i.e. when the total weight on each side is at most half of the grand total.  
• Such a point p is called a weighted median of {xᵢ} with weights {pᵢ}.  

3. Full Solution Approach  
1. Read N and the list of pairs (xᵢ, pᵢ).  
2. Sort the cities by coordinate xᵢ in nondecreasing order.  
3. Compute the total population W = Σ pᵢ.  
4. Scan the sorted list, maintaining a running sum S of populations.  
5. The first coordinate xⱼ at which S + pⱼ ≥ W/2 is a weighted median.  
   - At that point, the weight on the left is ≤ W/2 and the weight on the right is ≤ W/2.  
   - Any p in [xⱼ, xⱼ] (i.e. p = xⱼ) minimizes F(p).  
6. Print xⱼ with 5 decimal places.  
Overall time complexity: O(N log N) dominated by sorting.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;

    // Read cities: (coordinate, population)
    vector<pair<long long,long long>> city(N);
    for (int i = 0; i < N; i++) {
        cin >> city[i].first  // xᵢ
            >> city[i].second; // pᵢ
    }

    // Sort by coordinate xᵢ
    sort(city.begin(), city.end(),
         [](auto &A, auto &B) {
             return A.first < B.first;
         });

    // Compute total population
    long long total = 0;
    for (auto &c : city) {
        total += c.second;
    }

    // Find weighted median
    long long half = (total + 1) / 2; 
      // We use (total+1)/2 so that when total is even,
      // we pick the first coordinate where prefix ≥ total/2.
    long long prefix = 0;
    double answer = 0.0;
    for (auto &c : city) {
        prefix += c.second;
        if (prefix >= half) {
            // This coordinate is the weighted median
            answer = static_cast<double>(c.first);
            break;
        }
    }

    // Output with exactly 5 decimal digits
    cout << fixed << setprecision(5)
         << answer << "\n";

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))

    # Read and store (xᵢ, pᵢ)
    cities = []
    for _ in range(N):
        x = float(next(it))
        p = float(next(it))
        cities.append((x, p))

    # Sort by x-coordinate
    cities.sort(key=lambda cp: cp[0])

    # Total population
    total = sum(p for _, p in cities)
    half = total / 2.0

    # Find weighted median
    prefix = 0.0
    for x, p in cities:
        prefix += p
        if prefix >= half:
            # x is the optimal station location
            answer = x
            break

    # Print with 5 decimal places
    print(f"{answer:.5f}")

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