我们有一栋旧建筑,有 n + 2 列连续。这些柱子支撑着天花板。这些列位于坐标为 0 = x0 < x1 < ... < xn < xn + 1 的点上。最左边和最右边的列是特殊的,我们将它们称为轴承,其他列是普通的。
对于每根柱子,我们都知道它的耐用性 di。让我们考虑一个坐标为 x 的普通柱。假设最靠近左侧的列(轴承或普通)的坐标是 a,最靠近右侧的列(也是轴承或普通)的坐标是 b。在此任务中,我们假设该列支持从点 $${ \frac { a + x } { 2 } }$$ 到点 $${ \frac { x + b } { 2 } }$$ 的天花板段(这里两个分数都被视为实数除法)。如果由柱子支撑的天花板部分的长度超过di,那么柱子就无法支撑它,并且在一段时间后会崩溃,之后荷载将根据相同的原理在相邻柱子之间重新分配。
因此,普通列将崩溃一段时间,直到进程停止在某种状态。可以证明剩余列的集合不依赖于列崩溃的顺序。如果最后只剩下两根承重柱,那么我们就假设整个建筑在屋顶的重量作用下崩溃了。但如果除了承重柱之外,至少还保留一根普通柱,那么建筑物就不会倒塌。
为了使建筑物更坚固,我们可以在任意点(不一定是整数)0 < x' < xn + 1 处添加一根额外的任意耐久度 d' 的普通柱。如果点 x' 已经被一根普通柱占据,则用一根新柱代替。
你的任务是找出:添加的柱子的最低耐用性是多少才能使建筑物不会崩溃?
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 普通列的数量。
第二行包含 n + 2 个整数 x0, x1, ..., xn, xn + 1 (x0 = 0, xi < xi + 1 for 0 ≤ i ≤ n, xn + 1 ≤ 109) — 列的坐标。
第三行包含 n 个整数 d1, d2, ..., dn (1 ≤ di ≤ 109)。
输出
打印一个数字 - 为了使建筑物保持住而需要添加的柱的最低可能耐久性。如果您不必添加该列,请打印 0。您的答案将使用相对或绝对误差 10 - 4 进行检查。
示例
输入 #1
2 0 20 40 100 15 40
输出 #1
10
输入 #2
3 0 4 10 28 30 9 13 5
输出 #2
0