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

Правила

Правила

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

На двох, Сему i Юрi вже понад 80 рокiв. Коли вони збираються разом, на них нападає старечий маразм. Вони починають придумувати безлiч правил, якi всi, на їх думку, повиннi виконувати.

Користуючись своїм вагомим статусом в суспiльствi вони намагаються примушувати всiх до їх виконання.

От, наприклад, чим їм заважали дерева в парку? У парку росло n дерев, розмiщених на однiй лiнiї. Кожне дерево можна уявити вiдрiзком, один з кiнцiв якого розмiщений в точцi (x[i]; 0) (корiнь), а iнший — в точцi (x[i]; h[i]) (вершина дерева). Тут, x[i] — це координата дерева на прямiй, а h[i] — висота дерева.

Нове правило Сема i Юри стверджує, що вершина кожного дерева повинна бути освiтлена лiхтарем. Для цього, вершечки деяких дерев необхiдно зрiзати. Бiльш формально, лiхтар — це точка з координатами (x; y). Необхiдно зменшити висоту деяких дерев, щоб для кожного дерева вiдрiзок мiж лiхтарем i вершиною дерева не перетинався жодним iншим деревом. Якщо певне дерево дотикається до вiдрiзка мiж лiхтарем та вершиною дерева, то немає потреби його зрiзати. Зауважимо, що якщо зменшити висоту дерева до нуля, це все ще буде вважатися деревом.Вам, як учасникам олiмпiади, доведеться це правило виконувати. Тому знайдiть мiнiмальну сумарну довжину дерев, яку доведеться зрiзати.

Входные данные

Перший рядок мiстить одне цiле число n (1 ⩽ n ⩽ 10^5) — кiлькiсть дерев у парку.Кожний з наступних n рядкiв мiстить по два цiлi числа x[i] i h[i] (0 ⩽ x[i]10^9, 1 ⩽ h[i] ⩽ 1 000) — координати та висоти дерев, вiдповiдно.Наступний рядок мiстить два цiлi числа x та y (0 ⩽ x ⩽ 10^9, 1 ⩽ y ⩽ 1 000) — координати лiхтаря.Гарантується, що дерева заданi в порядку зростання координат, а також жодне дерево не має ту ж координати що лiхтар.

Выходные данные

В єдиному рядку виведiть одне число — мiнiмальну сумарну довжину дерев, яку треба буде зрiзати з абсолютною або вiдносною похибкою, яка не перевищує 10^(−6).Формально, нехай ваша вiдповiдь рiвна a, а вiдповiдь журi — b. Ваша вiдповiдь буде зарахована лише в тому випадку, якщо | a − b | / max( 1; |b| ) ⩽ 10^(−6).

Пример

Входные данные #1
7 4
2 4 1 2 2 3 2
Выходные данные #1
YES
Источник 2019-2020 ACM-ICPC, SEERC, 1/8 фiналу, 13 квiтня 2019 року