Задача №115165. N станков
Вы были приглашены в качестве специалиста по оптимизации производственных процессов в одну очень крупную компанию. У компании в распоряжении находятся \(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\) монет суммарно.
В первом тесте бюджет не позволяет нам сдвинуть станок \((*,~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\).
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