Чому корова перейшла дорогу III (Платина)

Обмеження на час виконання 2 секунди

Обмеження на використання пам'яті 256 мегабайтів

Фермер Джон продовжує дослідження переходів корів через дорогу, описану в двох попередніх задачах. Тепер він вважає породи корів a і b дружніми, якщо |a − b| ≤ k, і недружніми в протилежному випадку.

За заданим упорядкуванням порід на кожній зі сторін дороги, визначте кількість недружніх перехресних пар порід, де перехресні пари порід визначені в попередньому завданні.

Вхідні дані

Перша стрічка містить n (1 ≤ n ≤ 10^5) і k (0 ≤ k < n). Наступні n стрічок описують порядок за номерами порід на першій стороні дороги. Кожен номер породи - це число в інтервалі 1 .. n. Останні n стрічок описують порядок за номерами порід на другій стороні дороги. Кожен номер породи з'явиться рівно один раз в кожному порядку.

Вихідні дані

Виведіть максимальну кількість недружніх перехресних пар порід.

Приклади

Вхідні дані #1

Відповідь #1

Примітка

У цьому прикладі породи 1 і 4 недружні і перехресні, так само як і породи 1 і 3.

Відправки 4

Коефіцієнт прийняття 75%