Description

𝑁座楼房，立于城中。

第𝑖座楼，高度$h_i$。

你需要一开始选择一座楼，开始跳楼。在第𝑖座楼准备跳楼需要$c_i$的花费。

每次可以跳到任何一个还没有跳过的楼上去。但跳楼是有代价的，每次跳到另外一座楼的代价是两座楼高度的差的绝对值，最后一次从楼上跳到地面上不需要代价（只能跳到地上一次）。为在代价不超过𝑇的情况下，最多跳几次楼。

（一座楼只能跳一次，且每次跳楼都要计算准备的花费）

Format

Input

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

接下来一行𝑁个整数代表$c_i$。

接下来一行𝑁个整数代表$h_i$。

最后一行一个整数𝑇。

Output

一行一个整数代表答案。

Samples

4
3 5 4 11
2 1 3 1
17

3

Explanation

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

Range

对于30%的数据，1 ≤ 𝑁 ≤ 5。

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

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

对于100%的数据，1 ≤ 𝑁 ≤ 50,1 ≤ $c_i$, $h_i$ ≤ 10$^6$, 1 ≤ 𝑇 ≤ 10$^7$。

Limitation

1s, 256M for each test case.