P1412 Operation and Development

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.

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 a real number (rounded to $2$ decimal places) representing the maximum income.

### 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