ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Лучше поздно, чем никогда

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Джон против Санты

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ
Джон — обычный маленький мальчик. Правда, есть один нюанс. Он панически боится Санта-Клауса. Совсем скоро Рождество, и Джон решил подготовиться, чтобы не допустить появление бородатого волшебника в своём доме.
Так как обычно Санта проникает в дом через дымоход, Джон хочет заблокировать его. Дымоход в разрезе сбоку представляется в виде клетчатого прямоугольника h × w. В каждой клетке может либо находиться кирпич, либо нет. В силу специфики устройства дымохода в каждой горизонтальной линии не занятые кирпичами клетки образуют непустой непрерывный отрезок.
Санта-Клаус, в свою очередь, представляется в виде прямоугольника a × b клеток. За один шаг Санта может сдвинуться влево, вправо, вниз или вверх на одну клетку, но в любой момент времени он не должен пересекать занятые кирпичами клетки. Санта начинает свой путь над самой верхней горизонтальной линией и хочет закончить его под самой нижней горизонталью.
Джон собирается добавить в дымоход минимальное количество кирпичей так, чтобы Санта не смог попасть в дом. Обратите внимание, что после добавления кирпичей в каждой горизонтальной линии не занятые кирпичами клетки должны продолжать образовывать непустой непрерывный отрезок. В частности, нельзя полностью заблокировать некоторую горизонталь кирпичами.
Помогите Джону спасти своё Рождество!

Исходные данные

В первой строке даны целые числа h и w (1 ≤ h ≤ 105; 3 ≤ w ≤ 109) — высота и ширина дымохода соответственно.
Во второй строке даны целые числа a и b (1 ≤ a ≤ 109; 2 ≤ b ≤ 109) — высота и ширина прямоугольника, задающего Санта-Клауса, соответственно.
В следующих h строках описаны горизонтальные линии дымохода. Каждая линия задаётся двумя целыми числами li и ri (1 ≤ li, ri < w; 2 ≤ li + ri < w) — количествами кирпичей с левого и правого краёв соответственно.

Результат

В единственной строке выведите минимальное необходимое количество кирпичей. Обратите внимание, что ответ может равняться нулю.

Пример

исходные данныерезультат
7 5
1 2
2 1
1 1
1 1
1 1
2 1
1 1
1 1
1

Замечания

Иллюстрация к первому примеру (галочкой помечен кирпич, который нужно поставить, чтобы Санта не смог попасть в дом):
Problem illustration
Автор задачи: Никита Сивухин
Источник задачи: Контест "Лучше поздно, чем никогда"
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2136. Джон против Санты