Правила#8775
Містер Сем і містер Юрій, обидва старші за 80 років, мають надзвичайно сильну пристрасть до встановлення правил, яких, на їхню думку, усі повинні дотримуватися. Використовуючи свій суспільний вплив, вони намагаються запровадити ці правила повсюдно.
Розглянемо ситуацію в парку з деревами, що стоять в одну лінію. Кожне дерево можна уявити як вертикальний відрізок з основою в точці (x_i, 0) та вершиною в точці (x_i, h_i), де x_i — положення дерева вздовж лінії, а h_i — його висота.
Згідно з одним із їхніх останніх правил, вершину кожного дерева має освітлювати ліхтар. Щоб досягти цього, деякі дерева потрібно підрізати. Зокрема, ліхтар розташований у точці , і за правилом відрізок від ліхтаря до вершини кожного дерева не повинен перетинати жодне інше дерево. Якщо дерево лише доторкається до цього відрізка, обрізати його не потрібно. Навіть якщо висоту дерева зменшено до нуля, воно все одно вважається деревом.
Як учасники цього завдання, вам потрібно визначити мінімальну сумарну довжину, на яку необхідно обрізати дерева, щоб виконати правило.
У першому рядку задано одне ціле число (1 \leq n \leq 10^5) — кількість дерев у парку. У кожному з наступних рядків задано по два цілих числа x_i та h_i (0 \leq x_i \leq 10^9, 1 \leq h_i \leq 1000) — положення та висота кожного дерева. У наступному рядку задано два цілих числа та (0 \leq x \leq 10^9, 1 \leq y \leq 1000) — координати ліхтаря. Гарантується, що дерева подано у порядку зростання їхніх позицій, і жодне дерево не розташоване на одній точці з ліхтарем.
Виведіть одне число — мінімальну сумарну довжину, на яку потрібно обрізати дерева, забезпечивши абсолютну або відносну похибку, що не перевищує 10^{-6}. Формально, нехай ваша відповідь — , а правильна — . Ваш розв'язок буде прийнято, якщо |a-b| / \max(1,|b|) \leq 10^{-6}.
Приклад 1