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

2152. Таможенные пошлины

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ
Как известно, если вес посылки превышает mxw, получатель должен заплатить по a кредитов за каждый килограмм сверх mxw. Также, если стоимость товара превышает mxp кредитов, получателю необходимо доплатить b процентов от каждого кредита сверх mxp. Эти пошлины не считаются стоимостью посылки.
Недавно в таможню пришли сотрудники из СКБ Контур и установили новую систему, которая оцифровала информацию о всех посылках и автоматизировала подсчет доплаты. Егор обманом получил доступ к этой системе и теперь намеревается заработать на этом. Он собирается незначительно изменить данные не более чем у k посылок среди n лежащих на складе. Незначительно изменить данные — изменить ровно одну цифру либо у веса, либо у стоимости товара. Конечно, он хочет, чтобы в результате всех изменений пошлина со всех посылок вышла максимальной. За некоторый процент с прибыли он попросил Вас написать программу, которая решит за него эту задачу.

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

В первой строке через пробел записаны целые числа n и k (1 ≤ n ≤ 2 · 105), (0 ≤ kn) — количество посылок и количество возможных правок.
Во второй строке через пробел записаны целые числа mxw, mxp, a, b (1 ≤ mxw, mxp, a ≤ 109), (1 ≤ b ≤ 100).
В следующих n строках через пробел записаны целые числа wi и pi (1 ≤ wi, pi ≤ 109) — вес и цена i-й посылки.

Результат

Выведите одно действительное число — максимальную пошлинную выгоду от посылок. Ваш ответ считается правильным, если абсолютная или относительная его погрешность не превышает 10−9. Формально, пусть ваш ответ равен x, а ответ жюри равен y. Ваш ответ считается правильным, если |xy|max(1, |y|) ≤ 10-9.
Далее выведите n строк, в i-й из которых укажите через пробел новый вес и стоимость i-й посылки. Если существует несколько вариантов ответа, выведите любой из них.

Пример

исходные данныерезультат
4 2
30 500 4 30
6 1100
60 90
9 990
91 420
3217.000000000
6 9100
60 90
9 990
91 920
Автор задачи: Иван Сычёв