Across the River

All submissions for this problem are available.
Chef Ciel would like to make a bridge on the river in order to purchase cooking ingredients more easily. The river is an infinitely long straight line with width W. To be more specific, the river is a set of the all points on 0 ≤ y ≤ W in xyplane.
There are N piles on the river, and M types of wooden disks are available. The location of the kth pile is (X_{k}, Y_{k}). The kth type of wooden disks has radius R_{k}, and its price is C_{k} per disk.
Ciel can buy wooden disks as many as she likes, and Ciel can put them on the river. For each wooden disk, its center must be one of the locations (X_{k}, Y_{k}) of piles. Note that some part of wooden disks may be on the ground (y < 0, W < y) or other piles.
Ciel can move only on y = 0, on y = W, and on wooden disks. What is the minimum cost to make it possible to move from y = 0 to y = W.
Input
The first line contains an integer T, the number of test cases. Then T test cases follow. The first line for each test case has 3 spacesparated integers N, M and W. Next N lines has 2 spaceseparated integers X_{k} and Y_{k}. Then next M lines has 2 spaceseparated integers R_{k} and C_{k}.
Output
For each test case, print the minimum cost to make it possible to move from y = 0 to y = W. If it is impossible, print "impossible" without quotes.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 250
1 ≤ M ≤ 250
2 ≤ W ≤ 1000000000 (10^{9})
0 ≤ X_{k} ≤ 1000000000 (10^{9})
1 ≤ Y_{k} < W
1 ≤ R_{k} ≤ 1000000000 (10^{9})
1 ≤ C_{k} ≤ 1000000 (10^{6})
Sample
Input 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 Output 206 5 impossible
Explanation
The following figure indicates the optimal way for the first case.
Author:  laycurse 
Tester:  gamabunta 
Editorial  http://discuss.codechef.com/problems/RIVPILE 
Tags  dijkstra, july13, laycurse, medium, shortestpath 
Date Added:  19092011 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 