您被邀请作为生产流程优化专家到一家非常大的公司。该公司的工厂拥有 $$$n$$$ 机器,在生产链中一台一台地排列着。每台机器可以用以下两种方式之一进行描述:$$$(+,~a_i)$$$ 或 $$$(*,~a_i)$$$。
如果将值为 $$$x$$$ 的工件提供给 $$$(+,~a_i)$$$ 类型的机器,则输出工件的值为 $$$x + a_i$$$。
如果将值为 $$$x$$$ 的工件提供给 $$$(*,~a_i)$$$ 类型的机器,则输出工件的值为 $$$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$$$ 硬币,则可以实现的结果产品的最大值。
示例
输入 #1
3 2 1 3 * 2 + 1 + 1
输出 #1
6
输入 #2
4 2 2 2 * 2 + 1 * 3 + 2
输出 #2
21
输入 #3
8 2 1 1 * 2 + 1 * 4 + 1 + 1 + 1 * 5 + 3
输出 #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$$$。