题目描述

在繁华的 $A$ 市，矗立着 $n$座各具特色的高楼大厦，第$𝑖$座楼的高度为$h_i$。

每当你准备从第 $i$ 座楼的楼顶跳跃时，都会面临一个准备代价 $c_i$。

而在跳跃的过程中，代价的计算如下：每次跳到另一座楼，所需的代价是两座楼高度差的绝对值，即 $|h_i - h_j|$。不过，幸运的是，最后一次从楼上跳到地面时，这个代价是免费的（准备代价不会免费，最后一次跳到地面也算一次跳跃）。

你在一开始可以选择任意一座楼的楼顶作为起点，目标是在总代价不超过 $T$ 的前提下，尽可能多地进行跳跃。每座楼只能跳跃一次，且在每次跳跃之前都需要支付准备代价。

在这场跳跃的冒险中，你需要仔细规划每一步，合理安排跳跃的顺序，以确保在限制的代价内，可以跳跃最多次数。(一座楼只能到达一次，且每次跳跃都要计算准备的花费）

输入格式

第一行一个整数𝑁，代表楼的数量。

接下来一行𝑁个整数代表$𝑐_𝑖$。

接下来一行𝑁个整数代表$ℎ_𝑖$。

最后一行一个整数$𝑇$。

输出格式

一行一个整数代表答案。

样例1

4
3 5 4 11
2 1 3 1
17

3

从1号楼跳到2号楼再跳到3号楼再跳到地面是一种可行的方案。这样一共跳跃3次。

从3号楼跳到2号楼再跳到1号楼再跳到地面也是一种可行的方案。

从3号楼跳到1号楼再跳到2号楼再跳到地面也是一种可行的方案。

样例2

3
100 200 300
1 2 3
99

0

样例3

4
9 11 13 17
2 1 3 4
20

1

样例4

50
87 21 20 73 97 57 12 80 86 97 98 85 41 12 89 15 41 17 68 37 21 1 9 65 4 67 38 91 46 82 7 98 21 70 99 41 21 65 11 1 8 12 77 62 52 69 56 33 98 97
88 27 89 2 96 32 4 93 89 50 58 70 15 48 31 2 27 20 31 3 23 86 69 12 59 61 85 67 77 34 29 3 75 42 50 37 56 45 51 68 89 17 4 47 9 14 29 59 43 3
212

12

数据范围

对于$30\%$的数据，$1 ≤ N ≤ 5$

对于另外$20\%$的数据，所有$h_i$相同。

对于另外$20\%$的数据，$c_i=0$。

对于$100\%$的数据，$1 ≤ 𝑁 ≤ 50,1 ≤ 𝑐_𝑖 , ℎ_𝑖 ≤ 10^6 , 1 ≤ 𝑇 ≤ 10^7$。