Description

On a horizontal roadside, there are $n$ fishing lakes, numbered from left to right as $1,2,…,n$. Jiajia has $H$ hours of free time and hopes to catch as many fish as possible during this time. Starting from lake $1$, he moves to the right, choosing to spend some time (in multiples of $5$ minutes) fishing at certain lakes. He ends his fishing trip at one of the lakes. It takes Jiajia $5\times T_i$ minutes to walk from the $i$-th lake to the $(i+1)$-th lake. It is also measured that at the $i$-th lake, the first $5$ minutes of fishing yields $F_i$ fish, and for every subsequent $5$ minutes, the number of fish caught decreases by $D_i$. If the decreased number becomes negative, it is set to $0$. To simplify the problem, Jiajia assumes no one else is fishing and no other factors affect his expected catch. Write a program to determine the maximum number of fish Jiajia can catch.

Input Format

The first line contains an integer $n$, the number of lakes.

The second line contains an integer $H$, Jiajia's free time.

The third line contains $n$ integers, representing the number of fish caught in the first $5$ minutes at each lake.

The fourth line contains $n$ integers, representing the decrease in the number of fish caught every subsequent $5$ minutes at each lake.

The fifth line contains $n-1$ integers, where $T_i$ indicates the time taken to walk from the $i$-th lake to the $(i+1)$-th lake, which is $5\times T_i$ minutes.

Output Format

Output a single line with the maximum number of fish Jiajia can catch.

Sample 1

At the $1$st lake, fish for $15$ minutes, catching a total of $4+3+2=9$ fish;

At the $2$nd lake, fish for $10$ minutes, catching a total of $5+3=8$ fish;

At the $3$rd lake, fish for $20$ minutes, catching a total of $6+5+4+3=18$ fish;

Moving from the $1$st lake to the $2$nd lake and then to the $3$rd lake takes $15$ minutes in total. The total catch is $35$ fish, which is the maximum possible.

3
1
4 5 6
1 2 1
1 2

35

Data Range and Hints

For $100\%$ of the data, $2\le n\le 100, 1\le H\le 20$.