Фермер Джон продолжает исследование переходов коров через дорогу,
описанную в двух предыдущих задачах. Теперь он считает дружественными породы коров
\(a\) и \(b\), если if \(|a - b| \leq K\), и недружественными в противном случае.
По заданному упорядочению пород на каждой из сторон дороги, определите
количество недружественных пересекающихся пар пород, где пересекающиеся пары пород
определены в предыдущей задаче.
ФОРМАТ ВВОДА (файл friendcross.in):
Первая строка ввода содержит
\(N\) (
\(1 \leq N \leq 100,000\)) и
\(K\) (
\(0 \leq K < N\)).
Следующие
\(N\) строк описывают порядок по номерам пород, полей на первой стороне дороги.
Каждый номер породы - это число в интервале
\(1 \ldots N\). Последние
\(N\) строк описывают
порядок по номерам пород, полей на второй стороне дороги. Каждый номер породы появится
ровно один раз с каждом порядке.
ФОРМАТ ВВОДА (файл friendcross.out):
Выведите максимальное количество недружественных пересекающихся пар пород.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ
|
1
|
|
2
|
4
3
2
4
4
1
3
2
1
|
3
|
|
3
|
3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3
|
2
|
|
4
|
3
2 1
8 3
5 7
|
15
|
|
5
|
8
3 1
3 0
6 0
2 1
4 1
3 0
4 0
3 1
|
3
|
|
6
|
4 1
4
3
2
1
1
4
2
3
|
2
|
|
7
|
5 4
7
8
6
2
9
2 5
4 9
0 3
8 13
|
3
|
|
8
|
10 6 5
2
10
1
5
9
|
1
|
|
9
|
5
5
4
1
3
2
1
3
2
5
4
|
0
|
|
10
|
6
1
2
3
4
5
6
6
5
4
3
2
1
|
5
|
|
11
|
6
1
2
3
4
5
6
6
5
4
3
2
1
|
5
|
|
12
|
4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80
|
31
|