E - Painting Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は N 個のブロックが一列に並んだ塀のペンキ塗りを担当しています。各ブロック i （ 1 \leq i \leq N ）には現在の高さ H_i があります。

高橋君は M 本のローラーを持っています。ローラー j （ 1 \leq j \leq M ）は幅 W_j であり、連続するちょうど W_j 個のブロックをまとめて塗ることができます。

ローラーで連続する W_j 個のブロックをまとめて塗ると、その区間のすべてのブロックの見た目の高さが、区間内のブロックの高さの最大値に揃います。これは、ローラーが区間内で最も高いブロックの高さに合わせてペンキを塗るため、低いブロックにもその高さまでペンキが塗られるからです。ローラーで塗られなかったブロックの見た目の高さは元の高さのままです。

高橋君は M 本のローラーの中からちょうど 1 本を選び、塀の中の連続する区間を塗ります。ローラーの選び方と塗る区間の選び方を最適に決めたとき、全ブロックの見た目の高さの合計を最大化したいと考えています。

全ブロックの見た目の高さの合計の最大値を求めてください。

制約

  • 1 \leq N
  • 1 \leq M
  • N + M \leq 10^6
  • 1 \leq H_i \leq 10^9 （ 1 \leq i \leq N ）
  • 1 \leq W_j \leq N （ 1 \leq j \leq M ）
  • 入力はすべて整数

入力

N M
H_1 H_2 \ldots H_N
W_1 W_2 \ldots W_M
  • 1 行目には、ブロックの個数を表す N 、ローラーの本数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各ブロックの高さを表す H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
  • 3 行目には、各ローラーの幅を表す W_1, W_2, \ldots, W_M が、スペース区切りで与えられる。

出力

全ブロックの見た目の高さの合計の最大値を 1 行で出力せよ。

入力例 1

5 3
2 1 4 3 2
2 3 1

出力例 1

17

入力例 2

4 2
5 1 2 10
1 4

出力例 2

40

入力例 3

12 5
3 8 2 6 5 10 1 4 7 9 2 5
3 5 8 1 12

出力例 3

120

入力例 4

30 8
12 4 18 7 25 3 9 15 6 21 11 2 30 8 14 5 19 1 27 10 16 24 13 20 22 17 26 23 28 29
2 4 6 9 10 15 20 30

出力例 4

900

入力例 5

1 1
1000000000
1

出力例 5

1000000000

Score : 466 pts

Problem Statement

Takahashi is in charge of painting a fence consisting of N blocks arranged in a row. Each block i (1 \leq i \leq N) has an initial height of H_i.

Takahashi has M rollers. Roller j (1 \leq j \leq M) has a width of W_j and can paint exactly W_j consecutive blocks at once.

When a roller is used to paint a range of W_j consecutive blocks, the apparent height of all blocks in that range becomes equal to the maximum height among the blocks in the range. This is because the roller applies paint up to the height of the tallest block in the range, so even lower blocks are painted up to that height. The apparent height of the blocks not painted by the roller remains their original height.

Takahashi will choose exactly 1 roller from the M rollers and paint a consecutive range of blocks on the fence. He wants to maximize the sum of the apparent heights of all blocks by optimally choosing the roller and the range to paint.

Find the maximum possible sum of the apparent heights of all blocks.

Constraints

  • 1 \leq N
  • 1 \leq M
  • N + M \leq 10^6
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq W_j \leq N (1 \leq j \leq M)
  • All input values are integers.

Input

N M
H_1 H_2 \ldots H_N
W_1 W_2 \ldots W_M
  • The first line contains N, the number of blocks, and M, the number of rollers, separated by a space.
  • The second line contains H_1, H_2, \ldots, H_N, representing the height of each block, separated by spaces.
  • The third line contains W_1, W_2, \ldots, W_M, representing the width of each roller, separated by spaces.

Output

Print the maximum possible sum of the apparent heights of all blocks in a single line.

Sample Input 1

5 3
2 1 4 3 2
2 3 1

Sample Output 1

17

Sample Input 2

4 2
5 1 2 10
1 4

Sample Output 2

40

Sample Input 3

12 5
3 8 2 6 5 10 1 4 7 9 2 5
3 5 8 1 12

Sample Output 3

120

Sample Input 4

30 8
12 4 18 7 25 3 9 15 6 21 11 2 30 8 14 5 19 1 27 10 16 24 13 20 22 17 26 23 28 29
2 4 6 9 10 15 20 30

Sample Output 4

900

Sample Input 5

1 1
1000000000
1

Sample Output 5

1000000000