CF1753E.N Machines

You have been invited as a production process optimization specialist to some very large company. The company has $n$ machines at its factory, standing one behind another in the production chain. Each machine can be described in one of the following two ways: $(+,~a_i)$ or $(*,~a_i)$.

If a workpiece with the value $x$ is supplied to the machine of kind $(+,~a_i)$, then the output workpiece has value $x + a_i$.

If a workpiece with the value $x$ is supplied to the machine of kind $(*,~a_i)$, then the output workpiece has value $x \cdot a_i$.

The whole production process is as follows. The workpiece with the value $1$ is supplied to the first machine, then the workpiece obtained after the operation of the first machine is supplied to the second machine, then the workpiece obtained after the operation of the second machine is supplied to the third machine, and so on. The company is not doing very well, so now the value of the resulting product does not exceed $2 \cdot 10^9$.

The directors of the company are not satisfied with the efficiency of the production process and have given you a budget of $b$ coins to optimize it.

To optimize production you can change the order of machines in the chain. Namely, by spending $p$ coins, you can take any machine of kind $(+,~a_i)$ and move it to any place in the chain without changing the order of other machines. Also, by spending $m$ coins, you can take any machine of kind $(*,~a_i)$ and move it to any place in the chain.

What is the maximum value of the resulting product that can be achieved if the total cost of movements that are made should not exceed $b$ coins?

你作为生产流程优化专家，受邀来到一家规模庞大的公司。该公司工厂内有 $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$ 枚金币的前提下，所能获得的最终产品最大值是多少？

The first line contains four integers $n$, $b$, $p$ and $m$ ($1 \le n \le 10^6$, $1 \le b, p, m \le 10^9$) — the number of machine at the factory, your budget and costs of movements of both kinds of machines.

Each of the following $n$ lines contains description of a machine. The description begins with one of the following characters: "+" or "*", that denotes the kind of the machine. Then an integer $a_i$ follows ($1 \le a_i \le 2 \cdot 10^9$).

It's guaranteed that the current value of the resulting product does not exceed $2 \cdot 10^9$.

第一行包含四个整数 $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$。

Print one integer — the maximum value of the resulting product that can be achieved if the total cost of movements that are made does not exceed $b$ coins.

输出一个整数——在移动总花费不超过 $b$ 枚金币的前提下，所能达到的最大乘积值。

In the first example our budget is too low to move machine $(*,~2)$, but we can move both machines $(+,~1)$ to the beginning of the chain. So the final chain will be $(+,~1)$ $(+,~1)$ $(*,~2)$. If the workpiece with the value $1$ is supplied to the first machine, its value will be changed in the following way: $1, 2, 3, 6$.

In the second example we can move only one machine. Let's move machine $(+,~2)$ to the beginning of the chain. The final chain will be $(+,~2)$ $(*,~2)$ $(+,~1)$ $(*,~3)$. The value of the workpiece will be changed in the following way: $1, 3, 6, 7, 21$.

In the third example we can place machine $(*,~4)$ before the machine $(*,~5)$, and move machine $(+,~3)$ to the beginning of the chain. The final chain will be $(+,~3)$ $(*,~2)$ $(+,~1)$ $(+,~1)$ $(+,~1)$ $(+,~1)$ $(*,~4)$ $(*,~5)$. The value of the workpiece will be changed in the following way: $1, 4, 8, 9, 10, 11, 12, 48, 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$。