Optimal Fishing

You are given H hours and n lakes arranged in a line (numbered 1 to n from left to right). You start at lake 1 and can only move right. Between lake i and lake i+1, the travel time is given as \(5\times t_i\) minutes.

At lake i, if you fish for a 5‐minute interval, you initially catch \(f_i\) fish. For every subsequent 5‐minute interval at that lake, the number of fish you catch decreases by \(d_i\) (i.e. in the second interval you catch \(\max(f_i-d_i,0)\), in the third \(\max(f_i-2d_i,0)\), and so on). When the fish count for an interval drops to 0 or below, you simply catch 0 fish for that interval.

Your objective is to decide on a destination lake at which to end your journey and to distribute your remaining fishing intervals optimally among all lakes visited (from lake 1 up to your destination). Note that any travel time is deducted from your total available time. The total time available in minutes is \(60H\) and fishing can only be done in discrete 5‐minute intervals.

Formally, let the total number of 5‐minute intervals be \(T=\frac{60H}{5}=12H\) (an integer). If you decide to finish at lake k (1-indexed), then the available fishing intervals are \(T-\sum_{i=1}^{k-1} t_i\). Using these intervals, you must decide how many intervals to spend at each lake 1 through k. In each interval, you choose the lake with the highest current fish count (breaking ties by choosing the lake with the smallest index) and update its fish count to \(\max(\text{current}-d_i,0)\) for the next 5 minutes. Compute the maximum number of fish that can be caught by optimally choosing k and distributing the fishing intervals.

Note: All formulas are rendered in LaTeX format.

inputFormat

The input consists of four lines:

• The first line contains two integers \(H\) and \(n\) (\(H\) is the number of hours available, \(n\) is the number of lakes).
• The second line contains \(n\) integers: \(f_1, f_2, \dots, f_n\), where \(f_i\) is the number of fish that can be caught in the first 5-minute interval at lake i.
• The third line contains \(n\) integers: \(d_1, d_2, \dots, d_n\), where \(d_i\) is the decrease in fish count for each additional 5-minute interval at lake i.
• The fourth line contains \(n-1\) integers: \(t_1, t_2, \dots, t_{n-1}\), where \(t_i\) represents the time (in units corresponding to 5 minutes) needed to travel from lake i to lake i+1.

You may assume that all input values are positive integers and that \(60H\) is a multiple of 5.

outputFormat

Output a single integer representing the maximum number of fish that can be caught.

sample

1 2
10 2
2 1
1

33