题目描述

有 $n$ 个鱼塘排成一排，从左到右编号为 $1, 2, \ldots, n$。你有 $H$ 小时的空闲时间，从第 $1$ 个鱼塘出发，可以选择在某些鱼塘停留钓鱼，最终在某个鱼塘结束。

从第 $i$ 个鱼塘走到第 $i+1$ 个鱼塘需要 $5 \times t_i$ 分钟。在第 $i$ 个鱼塘停留时，第一个 $5$ 分钟可以钓到 $f_i$ 条鱼，之后每多钓 $5$ 分钟，鱼量减少 $d_i$ 条（鱼量不会变为负数）。

请计算最多能钓到多少条鱼。

输入格式

第一行：鱼塘数量 $n$。

第二行：时间 $H$（小时）。

第三行：$n$ 个整数 $f_1, f_2, \ldots, f_n$。

第四行：$n$ 个整数 $d_1, d_2, \ldots, d_n$。

第五行：$n-1$ 个整数 $t_1, t_2, \ldots, t_{n-1}$。

输出格式

一行一个整数，表示最多能钓到的鱼的数量。

样例

2
1
10 1
2 5
2

31

提示

数据范围

$1 \le H \le 16$，$2 \le n \le 25$，$1 \le f_i \le 200$，$0 \le d_i \le 20$，$1 \le t_i \le 20$。