1408 - 公交系统

Time Limit : 1 Second

Memory Limit : 256 MB

Submission: 673

Solved: 74

Description


因为中国人口众多,公共交通就显得很重要. 在传统城市公共交通系统中,公交车是一种很重要的工具。甚至现在还扮演了一种极其重要的角色。



X市的公交系统显得很独特。不像别的城市,该市公交系统是基于两站间的距离来计费的。下表描述了两站之间距离与费用的关系:



 































距离




费用




0<dist<=L1




C1




L1<dist<=L2




C2




L2<dist<=L3




C3




L3<dist<=L4




C4




dist>L4




没有这种票




表1



你的邻居是一位出名的吝啬鬼。他希望你能帮他计算出他列出表中两站间的最短花费,你能帮帮他吗?



为了简化这个问题,你可以假设所有的站都在一条直线上。我们仅用X坐标来描述每一个站的位置。


Input


输入文件包含多组数据。第一行包含一个整数T表示T组测试数据(T<=20)



每组数据第一行为8个数:L1, L2, L3, L4, C1, C2, C3, C4,每一个数都是不超过1,000,000,000的非负数,并且L1<=L2<=L3<=L4.



接下来两个整数n和m,表示n个站和m个询问。下面n行,每行一个数表示第i个站的x坐标。



下面m行,每行两个数表示询问的起点站和目标站。



在所有的询问中,起点站和目标站都不同。



对于每组数据有,2<=N<=100,0<=M<=500,每一个x坐标在-1,000,000,000 到1,000,000,000之间,并且没有两个x坐标相同。


Output


对于第T组测试数据第一行输出“Case T:”(没有引号)



对于每组询问,如果两个站可达,输出最小花费,否则输出“Station X and station Y 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.
hint
source
2008华东邀请赛
© 2015 HUST ACMICPC TEAM. All Right Reserved.