Gathering

locked

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 everyone 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 distance d away from everyone. Given that restriction, can you help them identify an intersection that minimizes the total distance everyone has to travel?

Input Format

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 Format

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 distance d of, output “impossible” instead.

Sample Input

Sample input 1:
5
3 1
4 1
5 9
2 6
5 3
10

Sample input 2:
5
3 1
4 1
5 9
2 6
5 3
5

Sample input 3:
5
3 1
4 1
5 9
2 6
5 3
4

Sample Output

Sample output 1:
18

Sample output 2:
20

Sample output 3:
impossible

Explanation

Source: 2014 ICPC Northwestern European Regional

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score