Optimize!

题意翻译

题意： 求 A 有多少长度为 len 的区 间中的数和 B 中的数完美匹配。两个数匹配当且仅当其和不小于 h。 (区间必须连续)

题目描述

Manao is solving a problem with the following statement: He came up with a solution that produces the correct answers but is too slow. You are given the pseudocode of his solution, where the function getAnswer calculates the answer to the problem: `<br></br>getAnswer(a[1..n], b[1..len], h)<br></br> answer = 0<br></br> for i = 1 to n-len+1<br></br> answer = answer + f(a[i..i+len-1], b, h, 1)<br></br> return answer<br></br><br></br>f(s[1..len], b[1..len], h, index)<br></br> if index = len+1 then<br></br> return 1<br></br> for i = 1 to len<br></br> if s[index] + b[i] >= h<br></br> mem = b[i]<br></br> b[i] = 0<br></br> res = f(s, b, h, index + 1)<br></br> b[i] = mem<br></br> if res > 0<br></br> return 1<br></br> return 0<br></br>`Your task is to help Manao optimize his algorithm.

输入输出格式

输入格式

The first line contains space-separated integers $ n $ , $ len $ and $ h $ ( $ 1<=len<=n<=150000; 1<=h<=10^{9} $ ). The second line contains $ len $ space-separated integers $ b_{1},b_{2},...,b_{len} $ ( $ 1<=b_{i}<=10^{9} $ ). The third line contains $ n $ space-separated integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ).

输出格式

Print a single number — the answer to Manao's problem.

输入输出样例

输入样例 #1

5 2 10
5 3
1 8 5 5 7

输出样例 #1

2