eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пари

Пари

Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB

Мірко і Славко грають з іграшковими звірятками. Спочатку вони обирають одну з трьох можливих дошок для гри, як показано на рисунку. Кожна дошка складається з клітин (показаних на рисунку кружками), організованих в одно-, дво- або тривимірну решітку.

Потім Мірко розташовує N звірят по клітинах.

Відстань між двома клітинами - це мінімальна кількість кроків, яку потрібно зробити звірятку, щоб переміститися з однієї клітини в іншу. За один крок звірятко може переміститись в довільну із сусідніх клітин (на рисунку сумідні клітини з'єднані відрізками).

Двоє звірят можуть чути одне одного, якщо відстань між їх клітинами не перевищує число D. Завдання Славка - підрахувати кількість пар звірят, які можуть чути одне одного.

Завдання

Напишіть програму, яка за заданим типом дошки, розташуванням усіх звірят на ній та числу D знаходить потрібну кількість пар звірят.

Вхідні дані

Перший рядок вхідних даних містить чотири цілих числа в такому порядку: - тип дошки B (1 ≤ B ≤ 3); - кількість звірят N (1 ≤ N ≤ 100 000); - максимальну відстань D, на якій двоє звірят можуть чути одне одного (1 ≤ D ≤ 100 000 000); - розмір дошки M (максимальна координата, яка може зустрітися у вхідних даних): - якщо B = 1, то M не буде перевищувати 75000000; - якщо B = 2, то M не буде перевищувати 75000; - якщо B = 1, то M не буде перевищувати 75.

Кожен з наступних N рядків містить по B цілих чисел, розділених одиничними пропусками - координати відповідного звірятка. Кожна координата знаходиться в діапазоні від 1 до M, включно. В одній клітині може розташовуватись більше одного звірятка.

Вихідні дані

Вихідні дані мають складатися з єдиного цілого числа - кількості пар звірят, які можуть чути один одного.

Приклад

Вхідні дані #1
1 6 5 100
25
50
50
10
20
23
Вихідні дані #1
4
Джерело IOI-2007, День 2