← 返回题目列表

AtCoder · awc0096_c

C. 给花坛浇水

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥负责管理一个狭长的花坛,其中包括 N 部分。

每个部分的编号从 1 to N,并且对于每个部分 i (1 \leq i \leq N), 当前土壤湿度 记录 A_i 。

为了给花坛浇水,高桥可以执行以下操作任意次数(可能是 0 次):

  • 选择一个整数 l 满意 1 \leq l \leq N - K + 1,并增加水分含量 1 对于每个 K 节中的连续节 l 至部分 l + K - 1.

的值 每次操作中选择的 l 可以自由决定,并且可以多次选择相同的值。请注意,此操作只能增加水分含量;它不能减少它们。

Takahashi 希望使每个部分的湿度水平完全等于其目标值。具体来说,他希望实现这样一种状态:对于所有人来说 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
  • 第一行包含整数 N 代表节数和整数 K 表示在一次操作中水分含量增加的连续部分的数量,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个部分的当前湿度水平,以空格分隔。
  • 第三行包含整数 B_1, B_2, \ldots, B_N 代表每个部分的目标湿度水平,以空格分隔。

输出

如果可以使每个部分的湿度精确等于其目标值,则输出所需的最少操作次数。如果不可能,则输出 -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