← 返回题目列表

Codeforces · 1753/E

E. N 台机器

中文机器翻译题面 查看原题

您被邀请作为生产流程优化专家到一家非常大的公司。该公司的工厂拥有 $$$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$$$。