输入文件： amusement.in
输出文件： amusement.out
时间限制： 2 秒
内存限制： 256 MB

题目描述

游乐园 “Puperland” 新开了一个巨大的绳索公园。公园的骄傲是一条由 $n$ 个平台组成的路线，平台按顺序连接：第 $1$ 个平台与第 $2$ 个平台相连，第 $2$ 个与第 $3$ 个相连，依此类推。连接第 $i$ 个平台和第 $i+1$ 个平台的绳索长度为 $l_i$。

为了安全，路线有如下限制：

1. 对于所有 $2 \le i \le n-1$，第 $i$ 个平台上同时最多允许 $p_i$ 人停留。第一个和最后一个平台足够坚固，可以容纳任意多人。
2. 第 $i$ 条绳索上同时最多允许 $r_i$ 人通过。
3. 对于每条绳索，给定一个最小安全距离 $d_i$，同一条绳索上同时行走的两个人之间的距离不能小于 $d_i$ 米。

开园当天来了 $m$ 名游客，他们都想走完整条路线。所有人一开始按队列顺序站在第一个平台上，路线开放后即可开始前进。游客必须按他们在第一个平台上的队列顺序沿路线移动，过程中不允许互相交换位置。所有游客都要到达第 $n$ 个平台并离开路线。

不同游客在不同绳索上的最大速度不同。第 $j$ 个游客在第 $i$ 条绳索上的最大速度为 $v_{i,j}$ 米/秒。他可以以 $0$ 到 $v_{i,j}$ 之间的任意速度在该绳索上移动，但必须满足安全距离限制。

管理员担心所有游客可能无法在闭园前走完路线。请计算所有游客走完整条路线所需的最短时间。

输入格式

第一行包含两个整数 $n,m$，表示平台数和游客数。

第二行包含 $n-2$ 个整数 $p_2,p_3,\ldots,p_{n-1}$，表示中间平台的人数限制。若 $n=2$，这一行为空。

第三行包含 $n-1$ 个整数 $r_1,r_2,\ldots,r_{n-1}$，表示每条绳索的人数限制。

第四行包含 $n-1$ 个整数 $l_1,l_2,\ldots,l_{n-1}$，表示每条绳索长度。

第五行包含 $n-1$ 个整数 $d_1,d_2,\ldots,d_{n-1}$，表示每条绳索上的最小安全距离。

接下来 $n-1$ 行，每行包含 $m$ 个整数，第 $i$ 行为

表示每位游客在第 $i$ 条绳索上的最大速度。

数据范围：

• $2 \le n \le 100$；
• $1 \le m \le 100$；
• $1 \le p_i,r_i,l_i \le 100$；
• $1 \le d_i \le l_i$；
• $1 \le v_{i,j} \le 100$。

输出格式

输出一个实数，表示所有游客走完整条路线所需的最短时间，单位为秒。

答案的相对误差或绝对误差不超过 $10^{-6}$ 即可。也就是说，若你的答案为 $p$，正确答案为 $a$，满足

即可通过。

样例 1 输入

2 1

1
30
2
2

样例 1 输出

15

样例 2 输入

3 2
1
2 2
10 10
5 5
2 2
1 2

样例 2 输出

17.5

难度评价