#214779. [ICPC 2025 Yokohama R] Minimizing Wildlife Damage

:::epigraph[A wild boar www.irasutoya.com] :::

The farmland you are cultivating consists of a certain number of plots arranged from west to east. Currently, each plot contains a certain amount of wheat; the amounts may differ across plots. All the wheat will be ready for harvest after a certain number of days.

One big problem you are facing is that a hungry wild boar comes from the west every night. If none of the plots have any wheat remaining, the boar just turns back. Otherwise, the boar goes to the westernmost plot that still has wheat and eats one unit of wheat there. The boar then continues by moving to the adjacent plot to the east and eating one unit of wheat, until it either encounters a plot with no wheat remaining or finishes eating at the easternmost plot, at which point it returns home.

To mitigate the damage, you plan to choose some plots (possibly none) and remove all the wheat from these plots today, so that the boar may return without eating too much wheat on subsequent days. After that, the boar continues to come every night, but there is nothing you can do to mitigate the damage further.

You are given one or more candidate days on which you may harvest. For each candidate harvest day, determine the maximum possible amount of wheat remaining for harvest on that day, assuming you remove all the wheat from optimally chosen plots. The optimal choice of plots may vary across candidate days.

The input consists of a single test case of the following format.

The integer is the number of plots (). Plots are numbered from 1 to , from west to east. The integer is the number of candidate harvest days (). For each , the integer is the number of units of wheat in plot (). For each , the integer is the number of days until the -th candidate harvest day (), that is, the boar comes times before that day.

Output lines. The -th line should contain an integer representing the maximum possible number of units of wheat remaining on the -th candidate harvest day.

样例输入 1

3 4
3 1 4
1
2
3
7

样例输出 1

6
5
4
0

样例输入 2

6 3
300 200 100 100 200 300
10
50
340

样例输出 2

1140
1000
560

For Sample Input 1, if you do not remove any wheat, the amounts of wheat in the plots change as follows.

Instead, if you remove the wheat from plot 2, the amounts change as follows.

This choice is optimal for all given candidate days.

For Sample Input 2, the optimal choices are as follows.

• For the first candidate day, removing nothing is optimal. The remaining amounts will be .
• For the second candidate day, removing the wheat from plot 3 is optimal. The remaining amounts will be .
• For the third candidate day, removing the wheat from plots 2 and 4 is optimal. The remaining amounts will be .