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

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

Инженер Джио проводит испытания новых сверхскоростных поездов. Поскольку поезда экспериментальные, у них не должно возникать трудностей при проезде через промежуточные города. Поэтому инженер Джио требует, чтобы ни в каком городе на пути поезда, кроме, может быть, начального и конечного, не было развилок. Точнее, из любого промежуточного города на пути поезда должны выходить либо ровно две дороги, ведущие в другие города (возможно, в один и тот же), либо ровно одна дорога, начинающаяся и заканчивающаяся в этом городе.

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

Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение \(A\), составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение \(B\).

Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.

Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении \(A\), совпадает с набором спичек, используемым в изображении \(B\). Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга).

Вася устал решать головоломки вручную, и теперь он просит вас написать, программу, которая будет решать головоломки за него. Программа будет получать описания изображений \(A\) и \(B\) и должна найти минимальное количество спичек, которые надо переложить в изображении \(A\), чтобы полученная картинка получалась из \(B\) параллельным переносом.

В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает привычное нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D.

Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.

Дано выражение в постфиксой записи, содержащее однозначные числа, операции +, –, *. Вычислите значение записанного выражения.

Вам необходимо нанять работников для строительного проекта. Заявление о приёме на работу подали N кандидатов, пронумерованных от 1 до N включительно. Каждый кандидат с номером k требует, чтобы в случае приёма его на работу ему платили не менее чем S_k долларов. Также для каждого кандидата с номером k известен его уровень квалификации Q_k. Положение о строительной деятельности требует, чтобы вы платили работникам пропорционально их уровню квалификации относительно друг друга. Например, если вы нанимаете двух работников A и B таких что Q_A = 3 * Q_B, то вы обязаны платить работнику A ровно в три раза больше, чем вы платите работнику B. Вам разрешается платить работникам нецелое число денег. Более того, разрешается даже платить количество денег, которое не может быть записано с помощью конечного числа десятичных цифр, такое как треть или шестую долю доллара.

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

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

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

Ограничения

1 ≤ N ≤ 500 000 Число кандидатов.

1 ≤ S_k ≤ 20  000 Минимальное требование к жалованию кандидата номер k.

1 ≤ Q_k £ 20 000Уровень квалификации кандидата номер k.

1 ≤ W ≤ 10 000 000 000Сумма денег, доступная вам.

Важное замечание

Максимальное значение W не может быть представлено 32-битным типом данных. Вам необходимо использовать 64-битный тип данных, такой как long long в C/C++ или int64 в Pascal, чтобы значение W можно было сохранить в одной переменной. Дополнительные подробности представлены на страницах с технической информацией.