Description

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.

Input Format

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 Format

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

5 4 3 2 1

82

Hint

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