← 返回题目列表

Codeforces · 471/D

D. MUH 和立方体墙

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

圣彼得堡动物园的北极熊 Menshykov 和 Uslada 以及基辅动物园的大象 Horace 在某处拿到了很多木块。他们开始通过将立方体一个一个地放在另一个顶部来制作立方体塔。他们将多座排成一排的塔定义为墙。墙可以由不同高度的塔组成。

霍勒斯是第一个完成墙的人。他称他的墙为大象。城墙由w个塔组成。熊们也完成了墙的建造,但他们没有给它命名。他们的城墙由n座塔组成。贺拉斯看着熊的塔楼,想知道:他在城墙上的多少个地方可以“看到大象”?如果该段上的塔楼高度与贺拉斯墙上的塔楼高度按顺序匹配,那么他可以在 w 个连续塔楼的一段上“看到大象”。为了看到尽可能多的大象,霍勒斯可以升高或降低他的墙。他甚至可以将墙壁降低到地面以下(请参阅示例图片以了解详情)。

你的任务是计算 Horace 可以“看到大象”的片段数量。

输入

第一行包含两个整数 n 和 w (1 ≤ n, w ≤ 2·105) — 相应的熊墙和大象墙中的塔的数量。第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 熊墙中塔的高度。第三行包含 w 个整数 bi (1 ≤ bi ≤ 109) — 象墙中塔的高度。

输出

打印熊墙上霍勒斯可以“看到大象”的部分的数量。

示例

输入 #1

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

输出 #1

2

注意

左图为样本中霍勒斯的墙,右图为熊的墙。霍勒斯可以“看到大象”的部分是灰色的。