Вы были приглашены в качестве специалиста по оптимизации производственных процессов в одну очень крупную компанию. У компании в распоряжении находятся \(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\) монет?
Выходные данные
Выведите одно целое число — максимальную ценность выходного продукта, которой можно добиться, переставив станки в цепи производства на не более чем \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 1 3
* 2
+ 1
+ 1
|
6
|
|
2
|
4 2 2 2
* 2
+ 1
* 3
+ 2
|
21
|
|
3
|
8 2 1 1
* 2
+ 1
* 4
+ 1
+ 1
+ 1
* 5
+ 3
|
240
|