M. Friendship
time limit per test
10 с
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ people standing in a line for the best dish at Andover - beef teriyaki. Knowing that people like to stick with their friends while waiting for food, Arnav observes that the $$$i$$$-th person in the line knows the $$$j$$$-th person if and only if $$$i-a_i\le j\le i + b_i$$$. If two people know each other, we say they are friends. How many pairs of friends are there in the line?

Input

The first line contains two integers $$$n$$$ $$$(1\le K\le n\le5\times10^5)$$$- the number of people in the line.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\le a_i\le n)$$$ - the elements of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ $$$(1\le a_i\le n)$$$ - the elements of the array $$$b$$$.

Output

Print the answer - the number of friends in the line.

Examples
Input
3
3 3 3
3 3 3
Output
3
Input
5
0 1 2 0 1
2 1 0 0 1
Output
3
Note

In the first example, there are 3 pair of friends, $$$(1,2),(1,3)$$$, and $$$(2,3)$$$.

In the second example, there are also 3 pair of friends, $$$(1,2),(1,3)$$$, and $$$(2,3)$$$.