Description

After the Computer Group classmates easily beat a carefully designed game made by a younger kid, he felt very upset. To comfort and encourage him, VIP999 decided to treat him to "Niannian Dafengshou" (pinyin), and to show sincerity, he also decided to go fishing himself.

However, since he still needs to prepare for NOIP 2013, Teacher z only gave him $H$ hours of free time. Suppose there are $n$ fish ponds along a horizontal road, numbered from left to right as $1, 2, 3, \dots, n$.

VIP is very efficient. He wants to catch as many fish as possible within this time. He starts from lake $1$ and walks to the right, optionally stopping at some lakes to fish for some time, and finally ends fishing at some lake. He measured that walking from lake $i$ to lake $i+1$ takes $5 \times t_i$ minutes, and when staying at lake $i$, the first $5$ minutes yield $f_i$ fish. After that, for every additional $5$ minutes of fishing, the number of fish decreases by $d_i$. To simplify the problem, assume there are no other anglers and no other factors affecting the expected number of fish he catches. Please write a program to compute the maximum number of fish he can catch.

Input Format

• Line 1: The number of lakes $n$.
• Line 2: Time $H$ (hours).
• Line 3: $n$ numbers: $f_1, f_2, \dots, f_n$.
• Line 4: $n$ numbers: $d_1, d_2, \dots, d_n$.
• Line 5: $n - 1$ numbers: $t_1, t_2, \dots, t_{n-1}$.

Output Format

One integer: the maximum number of fish that can be caught.

2
1
10 1
2 5
2

31

Hint

Constraints: $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$.

Translated by ChatGPT 5