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

Уральская региональная командная олимпиада по программированию 2019

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

J. Градостроение

Ограничение времени: 3.0 секунды
Ограничение памяти: 256 МБ
Ничто так не расслабляет Валю после тяжёлого контеста, как залипнуть в симулятор градостроения на весь вечер. Цель симулятора — построить идеальный город, настоящую утопию для многочисленных жителей. К сожалению, игра не всегда идёт гладко: у Вали кончаются то ресурсы, то терпение.
Сегодня Валя создал город с нуля. В нём уже есть n поселенцев, живущих в домах поодиночке. Они пронумерованы от 1 до n. Жители тут же высказали свои потребности: они хотят ходить друг к другу в гости, а для этого необходимо проложить дороги. Всего поступило m просьб. Просьба номер i поступила от жителя ai, который хочет в гости к жителю bi.
На данном этапе игры доступно всего два вида дорог: односторонняя и двусторонняя. Односторонняя дорога стоит x денежных единиц, а двусторонняя — y денежных единиц. Каждая дорога соединяет два дома. Ограничений на постройку дорог нет, в том числе между двумя домами можно проложить несколько дорог. Изначально не построено ни одной дороги.
Один житель сможет ходить в гости к другому, если существует путь по дорогам, соединяющий их дома. Путь может состоять из нескольких дорог. При этом по двусторонним дорогам можно ходить в любую сторону, а по односторонним — только по направлению дороги.
Определите наименьшее количество денежных единиц, на которые можно построить дороги так, чтобы удовлетворить все просьбы жителей. При этом не обязательно обеспечивать каждому жителю путь обратно домой.

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

В первой строке через пробел даны четыре целых числа: n, m, x и y — количество жителей, количество просьб, стоимость односторонней дороги и стоимость двусторонней дороги (2 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ x, y ≤ 109).
В каждой из следующих m строк через пробел даны два целых числа ai и bi, обозначающих, что житель номер ai хочет путь к жителю номер bi (1 ≤ ai, bin, aibi). Гарантируется, что все просьбы различны, то есть для любых ij верно aiaj или bibj.

Результат

В единственной строке выведите одно целое число — наименьшее количество денежных единиц, достаточное, чтобы выполнить все просьбы.

Примеры

исходные данныерезультат
4 3 2 3
1 2
1 3
2 3
4
4 3 2 3
1 2
1 3
2 1
5
4 4 2 3
1 2
2 1
1 3
3 1
6
Автор задачи: Валентин Зуев
Источник задачи: Уральская командная олимпиада по программированию 2019
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2147. Градостроение