题目描述

有 $N$ 个鱼塘排成一排，从第 $1$ 个鱼塘出发，可以在当前鱼塘钓鱼，也可以沿道路前往下一个鱼塘。

在第 $i$ 个鱼塘钓鱼的第 $1$ 分钟可以钓到 $f_i$ 条鱼。此后每多钓 $1$ 分钟，该分钟能钓到的鱼数减少 $d_i$，最低为 $0$。鱼数只与在这个鱼塘钓鱼的次数有关，不会随路上花费的时间减少。每次钓鱼的时间为整数分钟。

从第 $i$ 个鱼塘到第 $i+1$ 个鱼塘需要 $t_i$ 分钟。给定总时间 $T$，求最多能钓到多少条鱼。

输入格式

输入共 $5$ 行：

第一行一个整数 $N$。

第二行 $N$ 个整数 $f_i$。

第三行 $N$ 个整数 $d_i$。

第四行 $N-1$ 个整数 $t_i$；当 $N=1$ 时，此行为空行。

第五行一个整数 $T$。

输出格式

输出一个整数，表示最多钓到的鱼数。

样例

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

76

数据范围

$1\le N<100$，$1\le f_i\le1000$，$1\le d_i\le100$，$1\le t_i\le1000$，$1\le T<1000$。