Водитель маршрутки Сергей Александрович Жадных прославился своей феноменальной жадностью повсеместно. Он сам неоднократно заявлял, что за лишнюю копейку готов задушить родного брата и продать всех друзей. К сожалению, проверить эти слова не представлялось возможным, поскольку никакого брата, а также друзей, дома и семьи у Сергея Александровича не было. И что ещё хуже, денег у него тоже не было. Единственным достоянием г-на Жадных являлась старая маршрутка, на которой он и колесил по городу, подвозя редких пассажиров и время от времени осматривая краем глаза тротуары в поисках мелких монет...

В один из дней небеса сжалились на Сергеем Александровичем и решили прекратить его бесполезное существование в этом жестоком мире. С сей благой целью на голову ничего не подозревавшего г-на Жадных, вышедшего из маршрутки на призывный блеск 5-рублёвой монеты, свалился топор. Мечты о выгодной продаже бутылки мигом вылетели у него из головы, поскольку их место занял топор. В переносном смысле этого слова. Орудие небес не смогло пробить окостеневший череп г-на Жадных, однако, как выяснилось позднее, придало ему несколько весьма полезных свойств.

Вскоре после продажи топора Сергей Александрович обнаружил, что способен предвидеть будущее. Какие возможности, какие перспективы открылись незадачливому водителю маршрутки! Кто мы такие и куда идём? Чего бояться и на что надеяться? Ответы на эти вопросы г-на Жадных совершенно не интересовали. А вот на то, чтобы с помощью новых умений попытаться заработать немного денег, выполняя привычную работу, сообразительности у Сергея Александровича хватило.

Ежедневно маршрутка совершает один рейс от первой до N-й остановки. В маршрутке M мест для пассажиров. Вечером, просчитав линии вероятностей, г-н Жадных (между прочим, потенциальный Тёмный Иной шестого уровня) выяснил, что завтра на остановках маршрутку будут поджидать K человек. Для каждого человека были определены номер остановки S[i], на которой он желает сесть в маршрутку, и номер остановки F[i], на которой он собирается выйти. В соответствии с ценовой политикой Сергея Александровича, каждый пассажир должен заплатить P рублей за билет независимо от количества остановок. Более того, притормозив на остановке, г-н Жадных может выбирать, кого из желающих посадить в маршрутку, а кого нет. Ставя перед собой задачу максимизации прибыли, Сергей Александрович вполне разумно решил определить, каких именно людей нужно сажать в маршрутку. К сожалению, для этого его сил оказалось недостаточно. А Ваших?

Первая строка содержит целые числа N (2 ≤ N ≤ 100000), M (1 ≤ M ≤ 1000), K (0 ≤ K ≤ 50000) и P (1 ≤ P ≤ 10000). Каждая из следующих K строк содержит целые числа S[i] и F[i] (1 ≤ S[i] < F[i] ≤ N) для соответствующего человека.

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