1007 - 钓鱼

通过次数

0

提交次数

9

Time Limit : 1 秒
Memory Limit : 128 MB

    约翰是个垂钓谜,星期天他决定外出钓鱼h小时(1h16),约翰家附近共有n个池塘(2n25),这些池塘分布在一条直线上,约翰将这些池塘按离家的距离编上号,依次为L1,L2,,Ln,约翰家门外就是第一个池塘,所以他到第一个池塘是不用花时间的,约翰可以任选若干个池塘垂钓,并且在每个池塘他都可以呆上任意长的时间,但呆的时间必须为5分钟的倍数,(5分钟为一个单位时间),已知从池塘Li到池塘Li+1要化去约翰ti个单位时间,每个池塘的上鱼率预先也是已知的,池塘Li在第一个单位时间内能钓到的鱼为Fi0Fi100),并且每过一个单位时间在单位时间内能钓到的鱼将减少一个常数di0di100),现在请你编一个程序计算约翰最多能钓到多少鱼。

Input

输入第一行为一个整数n,第二行为一个整数h,第三行为n个用空格隔开的整数,表示Fii=1,2,,n),第四行为n个用空格隔开的整数,表示dii=1,2,,n),第五行为n-1个用空格隔开的整数,表示tii=1,2,,n-1

Output

输出一个整数,表示约翰最多能钓到的鱼的数量。

Examples

Input

2
1
10 1
2 5 
2

Output

31

Source

动态规划