P2198 Killing Ants

People say, "Good is rewarded with good, evil with evil; retribution only comes late, not never." Little FF focused only on growing his own business and ignored how his mining damaged the ecosystem on Greed Island, and the environment kept getting worse. Finally, the ants on the island mutated. They decided to attack Little FF’s mining area and drive humans off the island. Facing the ants’ offensive, humans lost ground one step after another. As a last resort, Little FF brought in SCV, the engineering robot sent by the strongest defense system manufacturer in the universe, hoping to hold off the ants’ assault.

After Little FF’s research, he found that the ants always attack along the same route of length $n$ units, and the time needed to traverse one unit length is $T$ seconds. In other words, as long as Little FF deploys defenses along this route and inflicts heavy damage on the ants, he can stop their advance. SCV specializes in building three kinds of defense towers: Laser Tower, Radiation Tower, and Interference Tower. On each unit length, exactly one tower can be built. Their effects are as follows: Laser Tower: Uses high-energy lasers and deals $r$ damage per second to the ants while they pass in front of the tower. Radiation Tower: Releases radioactive elements. After the ants pass this tower, they take $g$ damage per second. Interference Tower: Disrupts the ants’ pheromones. After the ants pass this tower, the time to traverse each subsequent unit length becomes $T + b$. The effects of Radiation Towers and Interference Towers stack. That is, if the enemy has passed $x$ Radiation Towers, then they take $x \times g$ damage per second; similarly, if they have passed $y$ Interference Towers, then the time to traverse one unit length becomes $T + y \times b$. There is enough time before the next wave of attacks. As the chief engineer of the “NewBe\_One” project, now appointed as the chief strategist, you must design a tower placement plan that maximizes the total damage dealt to the ants.

The input contains a single line with $5$ integers $n, r, g, b, T$ separated by a space. They represent: the total route length you can deploy on $n$, the Laser Tower’s per-second damage $r$, the Radiation Tower’s per-second damage $g$, the Interference Tower’s per-unit time increase $b$, and the base time per unit length $T$.

Output a single integer, the maximum total damage your plan can deal to the enemy.

#### Sample Explanation At position $1$ build a Radiation Tower; at positions $2$ and $3$ build Interference Towers; at positions $4$ and $5$ build Laser Towers. #### Constraints For $30\%$ of the testdata: $1 \leq n \leq 20$. For $60\%$ of the testdata: $1 \leq n \leq 1024, 0 \leq r,g,b \leq 65536, 0 \leq T \leq 3$. For the remaining $40\%$ of the testdata: $1 \leq n \leq 400, 0 \leq r,g,b \leq 2^{31}-1, 0 \leq T \leq 1000$. Translated by ChatGPT 5