#CW74. 序列(sequence)

序列(sequence)

sequence

题目描述

给定长度为 nn 的序列 a,ba,b。一次操作选择长度不超过 kk 的区间 [l,r][l,r],其中 1≤l≤r≤n1\le l\le r\le n 且 r−l+1≤kr-l+1\le k,把区间内所有数加一。求把 aa 变为 bb 的最少操作次数,不可能时输出 −1-1。

输入格式

从sequence.in文件中读入。

第一行输入 n,kn,k;第二、三行分别输入 a1,…,ana_1,\ldots,a_n 与 b1,…,bnb_1,\ldots,b_n。

输出格式

从sequence.out文件中输出。

输出答案或 −1-1。

样例

样例 11 输入

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

样例 11 输出

3

样例 22 输入

5 5
1 2 3 4 5
1 2 3 4 5

样例 22 输出

0

样例 33 输入

5 3
1 2 3 4 5
2 3 4 5 1

样例 33 输出

-1

数据范围

所有数据满足 1≤k≤n≤1061\le k\le n\le10^6、0≤ai,bi≤1090\le a_i,b_i\le10^9。

子任务 分值 附加条件
11 2020 n≤10n≤10
22 n≤103n≤10^3 且 ai,bi≤103a_i,b_i≤10^3
33 n≤106n≤10^6 且 k=nk=n
44 n≤106n≤10^6 且 ai,bi≤1a_i,b_i≤1
55 无附加限制