#4039. 集会

内存限制:256 MiB 时间限制:10 Sec

题目描述

Fictitia是一个很大的城市,他的街道由许多横向和纵向的街道垂直交叉组成,每两条相邻的横向街道距离为1,每两条相邻的横向街道距离也为1。每个十字路口有一个整数坐标(x,y)。所有的市民都居住在某个十字路口。
有一天,Fictitia中有一群不高兴的市民准备集会。他们想选一个十字路口(x’,y’)作为集会地点,使得所有人离集会地点的曼哈顿距离的总和最小。如果某个市民居住在(x,y),那么他与集会地点的曼哈顿距离为|x-x’|+|y-y’|。
但为了让所有人及时赶到,集会地点离每个市民的曼哈顿距离不能超过d。市民们想知道最小的距离总和为多少,如果不存在合理的集会地点,输出“impossible”。

输入格式

每个文件有多个输入数据,文件最后一行为一个数0。
对于每组输入数据
第一行为一个正整数n(n>=2),表示集会市民的人数。
接下来的n行,每行两个整数x,y(0<=x,y<=10^9),表示每个市民居住地点的坐标。
最后一行一个整数d(0<=d<=2*10^9),表示集会地点与每个市民居住地点的最大距离。

输出格式

对于每个测试输入,如果存在合理地点,输出一行,包含一个整数为最小的距离总和;否则输出一行“impossible”。

样例

样例输入


			
5
3 1
4 1
5 9
2 6
5 3
10
5
3 1
4 1
5 9
2 6
5 3
5
5
3 1
4 1
5 9
2 6
5 3
4
0

样例输出


			
18
20
impossible

数据范围与提示

100%的数据,n<=100000,每个文件中所有数据n的总和不超过300000