题目描述

有 $N$ 个鱼塘排成一排（$N<100$），每个鱼塘中有一定数量的鱼。例如，当 $N=5$ 时：

即：在第 1 个鱼塘中，钓鱼第 1 分钟内可钓到 10 条鱼，第 2 分钟内只能钓到 8 条鱼，……，第 5 分钟以后再也钓不到鱼了。从第 1 个鱼塘到第 2 个鱼塘需要 3 分钟，从第 2 个鱼塘到第 3 个鱼塘需要 5 分钟，……

给出一个截止时间 $T$（$T<1000$），请设计一个钓鱼方案。你从第 1 个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已经钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

输入格式

输入共 5 行：

• 第 1 行为 $N$；
• 第 2 行为各个鱼塘第 1 分钟能钓到的鱼的数量，数据之间用一个空格隔开；
• 第 3 行为各个鱼塘每过 1 分钟钓鱼数的减少量，数据之间用一个空格隔开；
• 第 4 行为从当前鱼塘到下一个相邻鱼塘所需的时间，共 $N-1$ 个整数；
• 第 5 行为截止时间 $T$。

输出格式

输出一个整数（不超过 $2^{31}-1$），表示最多能钓到的鱼的数量。

样例输入

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

样例输出

76

样例解释

一种最优安排是：在第 1 个鱼塘钓鱼 2 分钟，得到 $10+8=18$ 条鱼；花 3 分钟走到第 2 个鱼塘，钓鱼 2 分钟，得到 $14+10=24$ 条鱼；再花 5 分钟走到第 3 个鱼塘，钓鱼 2 分钟，得到 $20+14=34$ 条鱼。

总耗时为 $2+3+2+5+2=14$ 分钟，共得到 $18+24+34=76$ 条鱼。

文件读写

本题使用文件读写：从 fishing.in 读入，向 fishing.out 输出。