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

158. Commuter Train
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard input
output: standard output



You might have noticed that bus drivers sometimes pass by passengers waiting for the bus and stop at a place where the distance from the people to the bus doors is maximal. We don't know exact reasons of such behaviour, probably, this is done not because of some special wickedness of the driver but in order to allow passengers in the vehicle to get oR quicker. However, we know that in one country the government decided to implement automatic driving system on their commuter railroads. Among other features, this system is intended to automatically stop commuter trains at stations. A computer in the train is connected to a special radar, which determines passenger positions at the station platform. The computer decides where to stop the train in order to maximize the sum of the distances from each passenger to the closest door. All the hardware is ready, but the software project is late (transport problems). Your task is to implement this function for this software project.
More precisely, the station platform has length 0 < L <= 5000. There are 0 < M <= 300 passengers at the platform. Each passenger p has position Pp (0 <= P1 <= ... <= PM <= L) - the distance from the platform beginning to the passenger. There are 0 < N <= 300 doors in the train. Each door d has position Dd (0 = D1 < D2 < ... < DN <= L) - the distance from it to the door 1. The door width and the passenger sizes are not taken into account. For simplicity assume that the distance between a passenger i and a train door j is dist(i, j, S) = |Dj + S - Pi|, where S is train position - the distance between the first door and the beginning of the platform. Remember that the train must stop so that no door is outside of the platform.

Input
The file contains integer numbers separated by spaces and/or line feeds. At the beginning of the file there is the station description (L, M, and P1 ... PM), followed by the train description (N and D2 ... DN).

Output
You should output two numbers - the train position S, at which the maximal possible sum of the minimal distances between the passengers and the doors can be achieved and the sum itself. If there are many such train positions - output any one.

Sample test(s)

Input
Sample input #1
6
2
0 4
2
4

Sample input #2
4
5
0 1 2 3 4
4
1 2 3

Output
Sample output #1
2 4

Sample output #2
0.5 2.5

Note
Author:	Andrew Lopatin, Nikolay Durov
Resource:	ACM ICPC 2002-2003 NEERC, Northern Subregion
Date:	November, 2002

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

A platform spans positions \([0, L]\). There are \(M\) passengers at sorted integer positions \(P_1 \le \dots \le P_M\). A train has \(N\) doors: door 1 is at offset \(D_1=0\), and the rest are at strictly increasing integer offsets \(D_2,\dots,D_N\).

If the train stops with its first door at position \(S\), then door \(j\) is at \(S + D_j\). The train must fit entirely on the platform:
\[
0 \le S \le L - D_N.
\]

For each passenger \(i\), their distance to the closest door is:
\[
\min_j |(S + D_j) - P_i|.
\]

Find a stop position \(S\) maximizing the **sum** of these minimal distances over all passengers, and output \(S\) and the maximum sum. If multiple \(S\) work, output any.

Constraints: \(L \le 5000\), \(M,N \le 300\).

---

## 2) Key observations

1. **For a fixed passenger, distance to nearest door is piecewise-linear in \(S\)**  
   Each term \(\min_j |(S + D_j) - P|\) is the minimum of “V-shaped” functions, hence piecewise-linear with slope changes only when the nearest door changes.

2. **Nearest-door changes only at midpoints of adjacent doors**  
   A passenger switches from door \(j\) to \(j+1\) when they are exactly in the middle:
   \[
   P = S + \frac{D_j + D_{j+1}}{2}
   \Rightarrow
   S = P - \frac{D_j + D_{j+1}}{2}.
   \]
   Since \(P\) and \(D\) are integers, \(\frac{D_j + D_{j+1}}{2}\) is integer or half-integer, so these critical \(S\) are on the **0.5 grid**.

3. **Therefore an optimum exists at an integer or half-integer \(S\)**  
   The total sum (sum of piecewise-linear functions) reaches a maximum at some boundary point of its linear segments, hence at integer/half-integer positions.

4. **Avoid floating point by doubling coordinates**  
   Multiply everything by 2. Then half-integers become integers, and we can iterate all feasible \(S_2\) integer values:
   \[
   S_2 \in [0,\ 2L - 2D_N].
   \]

5. **Fast evaluation for a fixed \(S\): two-pointer scan**  
   Let passenger “relative coordinate” be \(T = P_2 - S_2\). We need the nearest door offset among sorted \(D_2\).  
   As passengers are sorted, \(T\) increases while scanning passengers, so the index of nearest door moves monotonically → a single pointer works, making evaluation \(O(M+N)\).

---

## 3) Full solution approach

### Step A: Read input
- Read \(L\), \(M\), passenger positions \(P_1..P_M\).
- Read \(N\), door offsets \(D_2..D_N\), and set \(D_1=0\).

### Step B: Convert to doubled coordinates
- \(L_2 = 2L\)
- \(P_{i,2} = 2P_i\)
- \(D_{j,2} = 2D_j\)
- Iterate \(S_2\) in integer steps (corresponding to 0.5 in original).

Feasible:
\[
0 \le S_2 \le L_2 - D_{N,2}.
\]

### Step C: Evaluate sum for each \(S_2\) efficiently
For each \(S_2\):
- Initialize door pointer \(j=0\), sum = 0.
- For each passenger in increasing order:
  - \(T = P_{i,2} - S_2\)
  - Move \(j\) forward while door \(j+1\) is closer than \(j\). The switch happens when:
    \[
    T > \frac{D_{j,2} + D_{j+1,2}}{2}
    \Longleftrightarrow
    2T > D_{j,2} + D_{j+1,2}.
    \]
  - Add \(|T - D_{j,2}|\) to the sum.

Track the best (maximum) sum and the corresponding \(S_2\).

### Step D: Output
Convert doubled integers back:
- if even → print as integer
- if odd → print as “x.5”

Complexity:
- Number of \(S_2\): at most \(2L \le 10000\)
- Each evaluation: \(O(M+N) \le 600\)  
Total \(\le 6 \times 10^6\) operations, fits easily.

---

## 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 l, m, n;
vector<int> p;
vector<int> d;

void read() {
    cin >> l >> m;
    p.resize(m);
    cin >> p;
    cin >> n;
    d.resize(n);
    d[0] = 0;
    for(int i = 1; i < n; i++) {
        cin >> d[i];
    }
}

void solve() {
    // This is more of an implementation problem. As the L is fairly small, we
    // can try all possible starts S on either the integer, or .5 grid, and
    // simply evaluate linearly how much the utility would be.

    int l2 = l * 2;
    vector<int> p2(m), d2(n);
    for(int i = 0; i < m; i++) {
        p2[i] = p[i] * 2;
    }
    for(int i = 0; i < n; i++) {
        d2[i] = d[i] * 2;
    }

    int max_s = l2 - d2[n - 1];

    int64_t best_sum = -1;
    int best_s = 0;

    for(int s = 0; s <= max_s; s++) {
        int64_t sum = 0;
        int j = 0;
        for(int i = 0; i < m; i++) {
            int target = p2[i] - s;
            while(j + 1 < n && 2 * target > d2[j] + d2[j + 1]) {
                j++;
            }
            sum += abs(target - d2[j]);
        }
        if(sum > best_sum) {
            best_sum = sum;
            best_s = s;
        }
    }

    auto print_half = [](int64_t x) {
        if(x % 2 == 0) {
            cout << x / 2;
        } else {
            cout << x / 2 << ".5";
        }
    };

    print_half(best_s);
    cout << " ";
    print_half(best_sum);
    cout << "\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def print_half(x2: int) -> str:
    """Convert doubled integer to string: even -> int, odd -> x.5."""
    if x2 % 2 == 0:
        return str(x2 // 2)
    return f"{x2 // 2}.5"

def solve() -> None:
    data = list(map(int, sys.stdin.read().split()))
    it = iter(data)

    # Platform
    L = next(it)
    M = next(it)
    P = [next(it) for _ in range(M)]  # already sorted in input

    # Train
    N = next(it)
    D = [0] * N
    for j in range(1, N):
        D[j] = next(it)

    # Double all coordinates to avoid floating point and allow step 0.5 enumeration.
    L2 = 2 * L
    P2 = [2 * x for x in P]
    D2 = [2 * x for x in D]

    # Train must fit: 0 <= S <= L - D_N  ->  0 <= S2 <= 2L - 2D_N
    max_s2 = L2 - D2[-1]

    best_sum2 = -1
    best_s2 = 0

    # Enumerate all half-integer S values via integer S2.
    for s2 in range(max_s2 + 1):
        total2 = 0
        j = 0  # current nearest door index

        # As we scan passengers in sorted order, target = p2 - s2 is sorted.
        for p2 in P2:
            target = p2 - s2

            # Advance j while door (j+1) is closer than door j:
            # target > (D2[j] + D2[j+1]) / 2  <=>  2*target > D2[j] + D2[j+1]
            while j + 1 < N and 2 * target > D2[j] + D2[j + 1]:
                j += 1

            total2 += abs(target - D2[j])

        if total2 > best_sum2:
            best_sum2 = total2
            best_s2 = s2

    sys.stdout.write(f"{print_half(best_s2)} {print_half(best_sum2)}\n")

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

