Gathering
The citizens of Fictitia have had enough! The city keeps getting bigger and bigger, and all the more boring. Fictitia consists of horizontal and vertical streets only. The distance between each pair of neighboring parallel streets is always the same; we take this as the unit distance. Surely some variation could not hurt?
In order to draw more support and make their unhappiness known to the municipality, a group of citizens has agreed to gather at an intersection of the city to protest. The question is:which intersection? Since there is not much difference between them, the idea was raised to select an intersection$ (x∗, y∗) $ that minimizes the total distance everyone has to travel. Since every-one lives close to an intersection, the individual distance travelled by someone who lives at $ (x, y) $ is given by $ |x−x∗|+|y−y∗| $.
However, this could present a problem for the people who live far away, since they might have trouble getting there in time.Therefore it was decided that the intersection should be at most a certain distanced away from everyone. Given that restriction, can you help them identify an intersection that minimizes the total distance everyone has to travel?
Input
The input consists of:
one line with one integer n (2 ≤ n ≤ 100000), the number of citizens;
n lines each with two integers x and y (0 ≤ x, y ≤ 109), the coordinates of each citizen’s house;
one line with one integer d (0 ≤ d ≤ 2×109), the maximum distance that each citizen should have to travel.
It is possible for multiple citizens to live at the same intersection.
Output
Output one line with a single integer: the smallest possible total distance that all citizens need to travel. If there is no intersection that everyone lives within a distanced of, output "impossible" instead.
Samples
| Input | Output |
|---|---|
5 3 1 4 1 5 9 2 6 5 3 10 | 18 |
| Input | Output |
|---|---|
5 3 1 4 1 5 9 2 6 5 3 5 | 20 |
| Input | Output |
|---|---|
5 3 1 4 1 5 9 2 6 5 3 4 | impossible |
This NWERC 2014 problem is licensed under the CC BY-SA 3.0 license.
You can find the original problem on the NWERC website.
