[SCOI2007] 最优驾车

题目描述

有n条南北方向的双向街道和n条东西方向的双向街道纵横交错。相邻街道(不管是哪个走向)的距离均为L英里。西南角交叉口的坐标为$(1,1)$,东北角为$(n,n)$。在所有交叉口均可任意改变行驶方向。每条街道有它自己的最高速度限制,该限制对整条街道有效(不管行驶方向如何)。 你的任务是从交叉口$(x_s,y_s)$开车行驶到$(x_t,y_t)$,要求只能在交叉口处改变速度,行驶过程中不得违反所在街道的速度限制,只能沿着路程最短的线路行驶,并且行驶时间在给定的闭区间$[t_1,t_2]$内。车速以“每小时英里数”为单位,它必须是$5$的正整数倍。若车速为$v$,则每加仑汽油能行驶的英里数为$80-0.03v^2$。

输入输出格式

输入格式


输入第一行为两个整数$n, L$。 第二行包含$n$个正整数,从南到北描述$n$条东西走向的街道的速度限制。 第三行包含$n$个正整数,从西到东描述$n$条南北走向的街道的速度限制。 第四行包含六个正整数$x_s, y_s, x_t, y_t, t_1, t_2$。

输出格式


如果无解,输出No。 否则输出两行,分别描述最早到达的方案(若有多种方案,选择其中最省油的)和最省油的方案(如果有多种方案,选择其中最早到达的)。每种方案用两个数表示,第一个数表示到达时刻(单位:分钟,向上取整);第二个数表示耗油量(单位:加仑,四舍五入保留两位小数)。

输入输出样例

输入样例 #1

6 20
30 40 50 50 50 50
50 50 50 50 50 40
1 1 6 6 300 320

输出样例 #1

300 6.25
318 5.60

输入样例 #2

8 2
10 20 20 30 10 20 10 10
10 20 20 30 10 20 10 20
6 8 2 4 10 39

输出样例 #2

No

说明

样例1的最快路线为以40英里/小时为速度匀速前进,路程为200英里,因此时间为5小时,每加仑汽油可以行驶80-0.03*40*40=32英里,因此耗油量为200/32=6.25加仑。 最省油路线是先以40英里/小时行驶120英里,然后以35英里/小时行驶80英里,耗油量为120/32+80/(80-0.03*35*35)=5.60加仑。下图的路线可以同时满足两种方案(其中第二种方案需要在(6,2)处改变速度)。 ![](https://cdn.luogu.com.cn/upload/pic/17708.png ) 20%的数据满足:n<=4 50%的数据满足:n<=8 100%的数据满足:1<=n<=10, 1<=l<=20, 0<=t1<=t2<=1000. 速度限制不超过50