Description

小吴是个垂钓谜，星期天他决定外出钓鱼h小时(1≤h≤16)，小吴家附近共有n个池塘(2≤n≤25)，这些池塘分布在一条直线上，小吴将这些池塘按离家的距离编上号，依次为L1, L2,…,Ln，小吴家门外就是第一个池塘，所以他到第一个池塘是不用花时间的，小吴可以任选若干个池塘垂钓，并且在每个池塘他都可以呆上任意长的时间，但呆的时间必须为5分钟的倍数，(5分钟为一个单位时间），已知从池塘 Li到池塘 Li+1要花去小吴ti个单位时间，每个池塘的上鱼率预先也是已知的，池塘Li在第一个单位时间内能钓到的鱼为Fi（0 ≤ Fi≤ 100），并且每过一个单位时间，在单位时间内能钓到的鱼将减少一个常数di（0 ≤ di≤ 100）

现在请你编一个程序计算小吴最多能钓到多少鱼。

Input Format

输入第一行为一个整数n，代表池塘的个数。

第二行为一个整数h，代表小吴外出钓鱼的时间。

第三行为n个用空格隔开的整数，表示Fi（i=1,2,…,n），代表每个池塘在第一个单位时间内能钓到的鱼。

第四行为n个用空格隔开的整数，表示di（i=1,2,…,n），代表每个池塘在单位时间内能钓到的减少的鱼的数量

第五行为n-1个用空格隔开的整数，表示ti（i=1,2,…,n-1），代表从池塘Li到池塘 Li+1花的时间

Output Format

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

2
1
10 1
2 5 
2

31

Source