CF1753E N Machines

你被邀请作为生产流程优化专家，前往一家非常大的公司。该公司在工厂中有 $n$ 台机器，依次排列在生产链上。每台机器可以用以下两种方式之一描述：$ (+,~a_i) $ 或 $ (*,~a_i) $。 如果一个数值为 $x$ 的工件被送入类型为 $ (+,~a_i) $ 的机器，则输出的工件数值为 $x + a_i$。 如果一个数值为 $x$ 的工件被送入类型为 $ (*,~a_i) $ 的机器，则输出的工件数值为 $x \cdot a_i$。 整个生产流程如下：数值为 $1$ 的工件被送入第一台机器，然后第一台机器操作后的工件被送入第二台机器，依此类推。由于公司经营不善，现在最终产品的数值不会超过 $2 \times 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 \times 10^9$）。 保证当前最终产品的数值不超过 $2 \times 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$。 由 ChatGPT 4.1 翻译