sequence
题目描述
给定长度为 n 的序列 a,b。一次操作选择长度不超过 k 的区间 [l,r],其中 1≤l≤r≤n 且 r−l+1≤k,把区间内所有数加一。求把 a 变为 b 的最少操作次数,不可能时输出 −1。
输入格式
从sequence.in文件中读入。
第一行输入 n,k;第二、三行分别输入 a1,…,an 与 b1,…,bn。
输出格式
从sequence.out文件中输出。
输出答案或 −1。
样例
样例 1 输入
5 3
0 0 0 0 0
1 2 1 0 1
样例 1 输出
3
样例 2 输入
5 5
1 2 3 4 5
1 2 3 4 5
样例 2 输出
0
样例 3 输入
5 3
1 2 3 4 5
2 3 4 5 1
样例 3 输出
-1
数据范围
所有数据满足 1≤k≤n≤106、0≤ai,bi≤109。
| 子任务 |
分值 |
附加条件 |
| 1 |
20 |
n≤10 |
| 2 |
n≤103 且 ai,bi≤103 |
| 3 |
n≤106 且 k=n |
| 4 |
n≤106 且 ai,bi≤1 |
| 5 |
无附加限制 |