该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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），现在请你编一个程序计算琪露诺最多能钓到多少鱼。

Format

Input

第一行为一个整数n， 第二行为一个整数h， 第三行为n个用空格隔开的整数，表示Fi（i=1，2，…，n）， 第四行为n个用空格隔开的整数，表示di（i=1，2，…，n）， 第五行为n-1个用空格隔开的整数，表示ti（i=1，2，…，n-1）。

Output

输出一个整数，表示琪露诺最多能钓到的鱼的数量。

Samples

2
1
10 1
2 5
2

31

Limitation

1s, 1024KiB for each test case.