Problem A
Astronomer

Астроном має пристрасть до спостереження за зірками. Зокрема, він отримує незміренне задоволення від спостереження за $k$ зірками одночасно через свій телескоп. Побудова телескопа з радіусом $r$ коштує $t\cdot r$ гривень. Новозбудований телескоп буде спрямований точно на початок координат $(0,0)$. Переміщення телескопа в іншу точку також вимагає зусиль; пересування телескопа на відстань $d$ одиниць коштує $s\cdot d$ гривень. Астроном може спостерігати всі зірки на відстані, не більшій за $r$ від місця, на яке спрямований телескоп.

Скільки коштує побудова та переміщення телескопа, який дозволяє спостерігати одночасно $k$ зірок?

Усі координати та відстані задані в Євклідовій площині.

Приклад

Ось приклад з $n=3$ зірками на позиціях $(0,0)$, $(2,0)$ та $(3,1)$. Заштрихована область показує телескоп з радіусом $1$, спрямований на $(1,0)$, який охоплює дві зірки; це коштує $s + t$ гривень та є оптимальним рішенням для вхідних даних з прикладу $3$. Зображення також показує оптимальні рішення для прикладів з вхідними даними $1$, $2$ та $4$.

Вхідні дані

Перший рядок містить чотири цілих числа: кількість $k$ зірок, які астроном хоче спостерігати, кількість $n$ зірок на сьогоднішньому небі, вартість переміщення $s$ та вартість побудови телескопа $t$. Потім слідують $n$ рядків, де $i$-й рядок містить цілочисельні координати $x_ i$ та $y_ i$ $i$-ї зірки.

Вихідні дані

Одне дійсне число: мінімальна сума грошей, яку астроном повинен витратити.

Обмеження та оцінювання

Ви можете припускати, що

1. $1\leq k\leq n\leq 700$.

2. $x_ i, y_ i\in \{ -10^9,\ldots , 10^9\} $ для всіх $i\in \{ 1,\ldots ,n\} $.

3. $s,t\in \{ 0,\ldots , 10^9\} $.

4. Ваш вивід буде прийнятий, якщо він знаходиться в межах відносної або абсолютної точності $\epsilon = 10^{-6}$ від правильної відповіді.

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

2 3 1000 500
0 0
2 0
3 1

1000.0

2 3 500 3000
0 0
2 0
3 1

3387.277541898787

2 3 250 750
0 0
2 0
3 1

1000.0

2 3 0 500
0 0
2 0
3 1

353.5533905932738

3 4 0 10
0 0
10 0
5 10
5 5

50.0