分数: 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