Maximizing Income in the 4X Exploit Model

In many PC strategy games the so-called $4X$ systems play an important role. The acronym comes from four English words starting with EX: explore, expand, exploit and exterminate. This problem focuses on the exploit part.

You pilot a spaceship equipped with a drill of initial power \(w\). Your ship will fly by \(n\) planets in a fixed order. Planets come in two types:

• Resource Planet: Contains mineral quality \(a_i\). If you decide to mine, you earn money equal to \(a_i \times p\), where \(p\) is the current drill power, and the drill loses \(k\%\) of its power, i.e. \(p \leftarrow p \times (1-0.01k)\).
• Repair Planet: Requires a maintenance fee of \(b_i\). If you choose to perform repairs, you pay \(b_i \times p\) money and your drill power is increased by \(c\%\), i.e. \(p \leftarrow p \times (1+0.01c)\). (Note that after repairs the drill's power may exceed its initial value.)

You may also opt to skip the action at any planet so that \(p\) remains unchanged and no money is exchanged. Money can be negative (you can go into overdraft).

Your task as the captain is to decide, for each planet, whether to take the profitable (or costly) action or skip it in order to maximize your total income. It can be shown that since all effects are multiplicative the problem can be reduced to a dynamic programming recurrence:

[ \begin{aligned} g(i) &= \max\Bigl{ &\text{if planet } i \text{ is resource:}\ &\quad a_i + (1-0.01k) \cdot g(i+1), \[6pt] &\quad \text{if planet } i \text{ is repair:} \[-4pt] &\quad -b_i + (1+0.01c) \cdot g(i+1), \[4pt] &\quad g(i+1) \Bigr}, \quad g(n+1)=0. \end{aligned} ]

The final answer is given by \(w \times g(1)\). All percentages are given as integers. Solve this problem to maximize your income.

inputFormat

The first line contains four numbers: an integer (n) (the number of planets), a real number (w) (the initial drill power), and two integers (k) and (c) representing the percentage decrease (for mining) and increase (for repair), respectively. The following (n) lines each contain two numbers: an integer (t) and a real number (x). If (t = 0), the planet is a resource planet with mineral quality (a_i = x); if (t = 1), the planet is a repair planet with maintenance cost (b_i = x).

outputFormat

Output a single real number: the maximum income achievable. Print the answer rounded to six decimal places.

sample

3 100 10 20
0 5
1 2
0 10

1400.000000