Maximizing Skiing Time in Vrsar

Vrsar is a seaside town composed of \(n\) hills. Viewed from the coast, the \(i\)-th hill is located at a distance of \(x_i\) meters. Each hill hosts an ice rink at its summit. All rinks open simultaneously every day, but the \(i\)-th rink closes after \(t_i\) minutes.

On each of the \(m\) days, Iva and Mia start their day at a distance \(a_i\) from the coast. When the rinks open, they begin their skating journey. They walk at a speed of 1 meter per minute and, because of their excellent fitness, require no extra time to climb to the hilltops. Once they arrive at a hilltop, they may skate for as long as they want until that rink closes. However, descending is not as easy as climbing: due to rain, the mountain paths are very slippery and descending from hill \(i\) takes an extra \(s_i\) minutes. After coming down from a hill, they may proceed to any other hill. If their starting position coincides with a hill’s base, they are considered to be at that hill’s foot.

The pair want to maximize their total skating time each day by visiting a sequence of hills. Consider an itinerary consisting of hills \(i_1, i_2, \dots, i_k\). They start at position \(a\), and for the first hill the arrival time is given by

\[ \text{arrival}_{i_1} = |x_{i_1} - a|, \]

and they can skate for

\[ \text{skate time at } i_1 = t_{i_1} - |x_{i_1} - a|. \]

After skating, they leave hill \(i_1\) at time \(t_{i_1}\) (since they must skate until the rink closes) and then descend, which takes \(s_{i_1}\) minutes. Therefore, the arrival time at the next hill \(i_2\) is

\[ \text{arrival}_{i_2} = t_{i_1} + s_{i_1} + |x_{i_2} - x_{i_1}|. \]

Similarly, the skating time at hill \(i_2\) equals

\[ \text{skate time at } i_2 = t_{i_2} - (t_{i_1} + s_{i_1} + |x_{i_2} - x_{i_1}|). \]

A hill can only be used if it is reached no later than its closing time, i.e. if \(\text{arrival} \le t_i\). Help Iva and Mia determine the maximum total skating time they can achieve in each day by optimally choosing the order in which they visit the hills. If no hill can be visited on a day, output 0.

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of hills and the number of days.

The second line contains \(n\) integers \(x_1, x_2, \dots, x_n\), where \(x_i\) is the distance (in meters) from the coast to the \(i\)-th hill.

The third line contains \(n\) integers \(t_1, t_2, \dots, t_n\) — the closing time (in minutes) for the ice rink on each hill.

The fourth line contains \(n\) integers \(s_1, s_2, \dots, s_n\) — the time required (in minutes) to descend hill \(i\).

The next \(m\) lines each contain one integer \(a_i\), the starting distance (in meters) from the coast on day \(i\).

outputFormat

For each day, output a single integer — the maximum total skating time (in minutes) that can be achieved if the hills are visited optimally. If no hill can be reached, output 0.

sample

3 3
1 4 10
10 15 30
2 5 3
0
2
5

20
22
25

</p>