C - Watering the Flower Bed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 個の区画からなる細長い花壇の管理を任されています。

各区画には 1 から N までの番号が付けられており、それぞれの区画 i（1 \leq i \leq N）には現在の土の水分量 A_i が記録されています。

高橋君は花壇に水をやるため、以下の操作を好きな回数（0 回でもよい）行うことができます。

  • 1 \leq l \leq N - K + 1 を満たす整数 l を 1 つ選び、区画 l から区画 l + K - 1 までの連続する K 個の区画それぞれの水分量を 1 増加させる。

各回の操作で選ぶ l の値は自由に決めてよく、同じ値を複数回選ぶこともできます。なお、この操作では水分量を増加させることのみが可能であり、減少させることはできません。

高橋君は、すべての区画の水分量をちょうど目標値にしたいと考えています。具体的には、すべての i（1 \leq i \leq N）について、区画 i の水分量がちょうど B_i に等しい状態を達成したいです。各区画の水分量が目標値と一致しなければ、不足していても超過していても達成とはみなしません。

すべての区画の水分量をちょうど目標値にすることが可能かどうか判定し、可能な場合は必要な最小の操作回数を求めてください。

制約

  • 1 \leq K \leq N \leq 3 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 入力はすべて整数
  • 目標値を達成可能な場合、最小の操作回数は 3 \times 10^{14} 以下であることが保証される（注：答えが32ビット整数の範囲を超える場合があります）

入力

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • 1 行目には、区画の個数を表す整数 N と、1 回の操作で水分量を増加させる連続する区画の個数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各区画の現在の水分量を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各区画の目標の水分量を表す整数 B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。

出力

すべての区画の水分量をちょうど目標値にすることが可能な場合は、必要な最小の操作回数を出力してください。不可能な場合は -1 を出力してください。出力は 1 行からなります。

入力例 1

5 3
0 0 0 0 0
1 1 3 2 2

出力例 1

3

入力例 2

3 2
0 0 0
0 1 0

出力例 2

-1

入力例 3

10 4
5 1 0 7 3 2 9 4 0 6
7 3 5 13 7 8 13 7 3 7

出力例 3

9

入力例 4

30 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 4 8 10 10 12 13 12 11 11 15 10 10 13 10 10 11 12 11 12 14 15 10 10 10 6 4 1 1

出力例 4

47

入力例 5

1 1
0
1000000000

出力例 5

1000000000

Score : 366 pts

Problem Statement

Takahashi is in charge of managing a long, narrow flower bed consisting of N sections.

Each section is numbered from 1 to N, and for each section i (1 \leq i \leq N), the current soil moisture level A_i is recorded.

To water the flower bed, Takahashi can perform the following operation any number of times (possibly 0 times):

  • Choose an integer l satisfying 1 \leq l \leq N - K + 1, and increase the moisture level by 1 for each of the K consecutive sections from section l to section l + K - 1.

The value of l chosen in each operation can be freely decided, and the same value may be chosen multiple times. Note that this operation can only increase moisture levels; it cannot decrease them.

Takahashi wants to make the moisture level of every section exactly equal to its target value. Specifically, he wants to achieve a state where, for all i (1 \leq i \leq N), the moisture level of section i is exactly equal to B_i. If any section's moisture level does not match its target value, it is not considered achieved, whether it is below or above the target.

Determine whether it is possible to make the moisture level of every section exactly equal to its target value, and if so, find the minimum number of operations required.

Constraints

  • 1 \leq K \leq N \leq 3 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • All inputs are integers
  • When achieving the target values is possible, it is guaranteed that the minimum number of operations is at most 3 \times 10^{14} (Note: the answer may exceed the range of 32-bit integers)

Input

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • The first line contains the integer N representing the number of sections and the integer K representing the number of consecutive sections whose moisture levels are increased in one operation, separated by a space.
  • The second line contains the integers A_1, A_2, \ldots, A_N representing the current moisture levels of each section, separated by spaces.
  • The third line contains the integers B_1, B_2, \ldots, B_N representing the target moisture levels of each section, separated by spaces.

Output

If it is possible to make the moisture level of every section exactly equal to its target value, output the minimum number of operations required. If it is impossible, output -1. The output consists of a single line.

Sample Input 1

5 3
0 0 0 0 0
1 1 3 2 2

Sample Output 1

3

Sample Input 2

3 2
0 0 0
0 1 0

Sample Output 2

-1

Sample Input 3

10 4
5 1 0 7 3 2 9 4 0 6
7 3 5 13 7 8 13 7 3 7

Sample Output 3

9

Sample Input 4

30 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 4 8 10 10 12 13 12 11 11 15 10 10 13 10 10 11 12 11 12 14 15 10 10 10 6 4 1 1

Sample Output 4

47

Sample Input 5

1 1
0
1000000000

Sample Output 5

1000000000