Problem1182--公交车站

1182: 公交车站

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 353  Solved: 134
[Submit] [Status] [Web Board] [Creator:]

Description

CS市有一条笔直的干道 , 干道上有 N 个公交车站,第i个公交车站的位置为 xi , 公交车在公交车站之间来回行驶 (乘客只能在公交车站上下车)。公交车有个里程表,如下图所示(比如说 a b两站之间的距离为 0<dist<=L1,那么乘客从 a 到b需要花费 C1元):


PIPI是个精明的人,他总是想用最便宜的价格从起点坐车到终点,你能告诉PIPI从某个起点 s 到终点 t的最小花费是多少吗??

Input

输入第一行包含测试用例组数 T。
对于每一组样例,第一行包括8个正整数 L1~L4 , C1~C4。
接下来两个正整数 N 和 M,代表公交站的个数和PIPI询问的次数。 (N<=500,M<=100000)。
接下来N行每行包括一个整数代表公交车站的位置。
接下来M行每行包括两个整数 s 和 t,代表PIPI询问的起点车站编号和终点车站编号 ( 1<=s,t <=N)。

Output

对于每组样例,首先输出Case数,然后对于每一次询问,若PIPI能从s到t,输出其最小花费。若不能从 s到t,输出"Station s and station t are not attainable."。详情请见样例输出。

Sample Input

2
1 2 3 4 1 3 5 7
4 2
1
2
3
4
1 4
4 1
1 2 3 4 1 3 5 7
4 1
1
2
3
10
1 4

Sample Output

Case 1:
The minimum cost between station 1 and station 4 is 3.
The minimum cost between station 4 and station 1 is 3.
Case 2:
Station 1 and station 4 are not attainable.

Source/Category

简单