UOJ Logo Sharp Sword 剑锋 OI

SSOI

#56. river

统计

【问题描述】

    搭一座跨过河的桥,河是一条无限长的宽度为W的直线,所有在xy坐标系中符合0<=y<=W的点都属于这条河流。河面上有N个木桩,还有M种可以用的木头的圆盘,第k个木桩的坐标为(Xk,Yk)。第k种圆盘的半径为Rk,价格为Ck。
    可以购买任意多的圆盘,而且可以把他们放在河面上,每一个圆盘的中心必须为某一个木桩的位置。注意,某些圆盘的一部分可以在地面上(即y<0或者y>W)。
    只能在直线y=0或者y=W或圆盘上移动(可以从一个圆盘移动到与其相机或相切的另一个圆盘)。请问从直线y=0到直线y=W修建一座可以走过去的桥的最少的费用。

【输入格式】

第一行一个整数T,代表测试数据的数量,接下来T组数据:
每组数据的第一行有三个空格隔开的整数N,M,W。
接下来N行,每行2个空格隔开的整数Xk和Yk。
接下来M行,每行2个空格隔开的整数Rk和Ck。

【输出格式】

对于每组数据输出从直线y=0到直线y=W修建一座可以走过去的桥的最少花费。假如这是不可能,那么输出"impossible"。

【输入样例1】

3
11 4 13
19 10
8 7
11 4
26 1
4 2
15 4
19 4
1 9
4 6
19 5
15 10
2 1
3 100
4 10000
5 1000000
11 4 13
19 10
8 7
11 4
26 1
4 2
15 4
19 4
1 9
4 6
19 5
15 10
2 1
3 2
4 3
5 4
1 1 1000000000
0 500000000
1 1

【输出样例1】

206
5
impossible

【时空限制】

时间限制:2S
空间限制:256MB
8a454fd603ad091c.png