题目描述

有 $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

样例解释

答案：76

枚举所有可能的终点

最优方案详解（最远到第 3 个鱼塘）

走到第 3 个鱼塘需要经过：

• 1 号 → 2 号：$3$ 分钟
• 2 号 → 3 号：$5$ 分钟

路上共花费 $8$ 分钟，还剩 $14-8=6$ 分钟可以钓鱼。

6 分钟的钓鱼过程：

总计： $20 + 14 + 14 + 10 + 10 + 8 = \boxed{76}$