Why Did the Cow Cross the Road III (Platinum)

Farmer John is continuing to ponder the issue of cows crossing the road through his farm, introduced in the preceding two problems. He realizes now that the threshold for friendliness is a bit more subtle than he previously considered - breeds a and b are now friendly if |a − b| ≤ k, and unfriendly otherwise.

Given the orderings of fields on either side of the road through FJ's farm, please count the number of unfriendly crossing pairs of breeds, where a crossing pair of breeds is defined as in the preceding problems.

Input

The first line contains n (1 ≤ n ≤ 10^5) and k (0 ≤ k < n). The next n lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range 1 .. n. The last n lines describe the order, by breed ID, of the fields on the other side of the road. Each breed ID appears exactly once in each ordering.

Output

Print the number of unfriendly crossing pairs of breeds.

Examples

Note

In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.