Gathering

The citizens of Fictitia have had enough. The city keeps growing, and it keeps getting more boring. Fictitia has horizontal and vertical streets only, and the gap between two neighbouring parallel streets is always the same. Take that gap as distance $1$.

To make their unhappiness known to the city council, a group of citizens agreed to gather at one intersection and protest. The question is which intersection. The intersections are much alike, so someone proposed picking the intersection $(x^*, y^*)$ that minimises the total distance everyone has to travel. Every citizen lives next to an intersection, so a citizen living at $(x, y)$ travels $|x - x^*| + |y - y^*|$.

This could be a problem for the citizens who live far away, because they might not get there in time. The group therefore decided that the chosen intersection has to be at most a distance $d$ away from every citizen. Under that restriction, find an intersection that minimises the total distance everyone has to travel.

• The first line has one integer $n$ ($2 \le n \le 100000$), the number of citizens.
• Each of the next $n$ lines has two integers $x$ and $y$ ($0 \le x, y \le 10^9$), the coordinates of one citizen's house.
• The last line has one integer $d$ ($0 \le d \le 2 \times 10^9$), the maximum distance each citizen should have to travel.

Several citizens can live at the same intersection.

Print one line with a single integer, the smallest possible total distance that all citizens have to travel. If no intersection lies within distance $d$ of every citizen, print impossible instead.