33OJ
登录 注册

#P17746. 「RSOI-1C」序列 / sequence

「RSOI-1C」序列 / sequence

背景

题目来源:【HT-121-Div.3】核桃 CSP-J 组模拟赛

题目描述

小 R 有两个长度为 nn 的序列 aa 和 bb。

他可以执行此操作任意次(也可以不执行):

  • 选一个长度 ≤k\leq k 的区间 [l,r][l, r](即 1≤l≤r≤n1\le l\le r\le n 且 r−l+1≤kr-l+1 \le k),把 al∼ara_l \sim a_r 都 +1+1。

现在,他问你最少需要多少次才可以让 aa 与 bb 相同。如果不可能输出 −1-1。

输入格式

输入共三行。

第一行,两个正整数 n,kn,k。

第二行,nn 个整数 a1,a2,…,ana_1, a_2 ,\dots, a_n。

第三行,nn 个整数 b1,b2,…,bnb_1,b_2 ,\dots, b_n。

输出格式

输出一行一个整数,表示答案。

5 3
0 0 0 0 0
1 2 1 0 1
3
5 5
1 2 3 4 5
1 2 3 4 5
0
5 3
1 2 3 4 5
2 3 4 5 1
-1

提示

【样例解释 #1】

依次选择 [1,3],[2,2],[5,5][1,3], [2,2], [5,5] 可使 a=ba=b。可以证明没有其他方案可以以更少的次数达到目标。

【样例解释 #2】

无需操作,序列 aa 与序列 bb 相同,故输出 0。

【样例解释 #3】

可以证明,序列 aa 不可能操作成序列 bb,故输出 -1。

【数据范围】

对于所有测试数据,保证:1≤k≤n≤106,0≤ai,bi≤1091\le k \le n \le 10^6,0 \le a_i,b_i \le 10^{9}。

::cute-table{tuack}

子任务编号 k≤n≤k \le n \le ai,bi≤a_i,b_i \le 特殊性质 分值
11 1010 无 2020
22 10310^3
33 10610^6 10910^9 k=nk = n
44 11 无
55 10910^9