Description

The $4X$ concept system refers to a widely used and mature system in PC strategy games, named after four English words that all begin with EX.

• $\verb!eXplore!$ (exploration)
• $\verb!eXpand!$ (expansion and development)
• $\verb!eXploit!$ (operation and development)
• $\verb!eXterminate!$ (conquest)

— Wikipedia

This time we focus on the exploit part and simplify its model:

You pilot a spaceship with a drill (initial capability value $w$), flying in a fixed route through $n$ planets in order. Planets are broadly divided into $2$ types: resource and maintenance. (Let $p$ be the current capability of the drill.)

1. Resource type: mineral mass $a_i$. If you choose to mine, you gain $a_i \times p$ money, and then the drill wears by $k\%$, i.e., $p \gets p \times (1 - 0.01k)$.
2. Maintenance type: maintenance fee $b_i$. If you choose to repair, you pay $b_i \times p$ money, and then the drill is restored by $c\%$, i.e., $p \gets p \times (1 + 0.01c)$.

Note: After maintenance, the drill’s capability value can exceed the initial value (you can think of it as refurbishment + upgrade).

Your balance may go into overdraft.

As the captain, make careful choices to maximize income.

Input Format

The first line contains $4$ integers $n, k, c, w$.

The next $n$ lines each contain $2$ integers $\mathrm{type}, x$.

• If $\mathrm{type} = 1$, it is a resource planet and $x$ is its mineral mass $a_i$.
• If $\mathrm{type} = 2$, it is a maintenance planet and $x$ is its maintenance fee $b_i$.

Output Format

Output a real number (rounded to $2$ decimal places) representing the maximum income.

5 50 50 10
1 10
1 20
2 10
2 20
1 30

375.00

Hint

Constraints

• For $30\%$ of the testdata, $n \le 100$.
• For another $20\%$ of the testdata, $n \le 1000$, $k = 100$.
• For $100\%$ of the testdata, $n \le 100000$, $0 \le k, c, w, a_i, b_i \le 100$, and the answer is guaranteed not to exceed $10^9$.

Translated by ChatGPT 5