E. N станков
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы были приглашены в качестве специалиста по оптимизации производственных процессов в одну очень крупную компанию. У компании в распоряжении находятся $$$n$$$ станков, стоящих друг за другом в цепочке производства. Каждый станок можно охарактеризовать одним из двух способов: $$$(+,~a_i)$$$ или $$$(*,~a_i)$$$.

Если на вход станку вида $$$(+,~a_i)$$$ подается заготовка с ценностью $$$x$$$, то на выходе получается заготовка с ценностью $$$x + a_i$$$.

Если на вход станку вида $$$(*,~a_i)$$$ подается заготовка с ценностью $$$x$$$, то на выходе получается заготовка с ценностью $$$x \cdot a_i$$$.

Весь производственный процесс выглядит следующим образом. На вход первому станку подается заготовка с ценностью $$$1$$$, полученная после работы первого станка заготовка подается на вход второму станку, результат его работы — на вход третьему станку и так далее. Дела у компании идут не очень хорошо, так что на данный момент ценность полученного на выходе продукта не превосходит $$$2 \cdot 10^9$$$.

Директора компании не довольны эффективностью производственного процесса и выделили вам бюджет в $$$b$$$ монет на его оптимизацию.

Чтобы оптимизировать производство, вы можете менять порядок станков в цепочке. А именно, потратив $$$p$$$ монет, вы можете взять любой станок вида $$$(+,~a_i)$$$ и переставить его в любое место в цепочке производства, не меняя порядок остальных станков. Также, потратив $$$m$$$ монет, вы можете взять любой станок вида $$$(*,~a_i)$$$ и переставить его в любое место в цепочке производства.

Какой максимальной ценности выходного продукта можно добиться, если сделать перестановки суммарной стоимостью не более $$$b$$$ монет?

Входные данные

Первая строка содержит четыре целых числа $$$n$$$, $$$b$$$, $$$p$$$ и $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le b, p, m \le 10^9$$$) — количество станков на производстве, ваш бюджет и стоимости переноса станков обоих видов.

Каждая из следующих $$$n$$$ строк содержит описание очередного станка. Описание станка начинается с символа «+» или «*», обозначающего вид станка. Далее следует целое число $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot 10^9$$$).

Гарантируется, что текущая ценность выходного продукта не превосходит $$$2 \cdot 10^9$$$.

Выходные данные

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

Примеры
Входные данные
3 2 1 3
* 2
+ 1
+ 1
Выходные данные
6
Входные данные
4 2 2 2
* 2
+ 1
* 3
+ 2
Выходные данные
21
Входные данные
8 2 1 1
* 2
+ 1
* 4
+ 1
+ 1
+ 1
* 5
+ 3
Выходные данные
240
Примечание

В первом тесте бюджет не позволяет нам сдвинуть станок $$$(*,~2)$$$, однако мы можем переместить оба $$$(+,~1)$$$ в начало, и получить цепочку $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(*,~2)$$$. Если ей на вход подать заготовку ценности $$$1$$$, то ее ценность будет меняться следующим образом: $$$1, 2, 3, 6$$$.

Во втором тесте мы можем сдвинуть только один станок. Переместим $$$(+,~2)$$$ из конца в начало получим цепочку $$$(+,~2)$$$ $$$(*,~2)$$$ $$$(+,~1)$$$ $$$(*,~3)$$$ при проходе через которую ценность заготовки меняется следующим образом: $$$1, 3, 6, 7, 21$$$.

В третьем тесте поместим станок $$$(*,~4)$$$ перед $$$(*,~5)$$$ и станок $$$(+,~3)$$$ в начало. Получим цепочку $$$(+,~3)$$$ $$$(*,~2)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(+,~1)$$$ $$$(*,~4)$$$ $$$(*,~5)$$$, при проходе через которую ценность заготовки меняется так: $$$1, 4, 8, 9, 10, 11, 12, 48, 240$$$.