Maximizing Ant Damage

After careful research, Little FF discovered that the ants always attack along the same path of length \(n\) units. The ants take \(T\) seconds to traverse one unit length. In other words, if Little FF can deploy defenses along the path and inflict significant damage on the ants, their advance can be halted.

SCV is adept at constructing three types of defensive towers, each of which can be built on one unit of the path. The towers work as follows:

• Laser Tower: Emits high‐energy lasers. When an ant passes the tower, it suffers \(r\) points of damage per second for the duration it takes to traverse that unit.
• Radiation Tower: Releases radioactive elements. After an ant passes such a tower, for every second thereafter it takes additional damage of \(g\) points. The effects stack; if the ant has passed \(x\) radiation towers before, it suffers \(x \times g\) damage per second.
• Interference Tower: Disrupts the ants’ pheromone trails. After an ant passes an interference tower, the time needed to traverse every subsequent unit increases by \(b\) seconds. That is, if the ant has passed \(y\) interference towers so far, each future unit is traversed in \(T+y \times b\) seconds.

Note that the effects of radiation towers and interference towers are cumulative. Now, with plenty of time before the next ant assault, you, as the chief strategist of the "NewBe_One" project, are tasked with designing a tower deployment plan that maximizes the total damage inflicted upon the ants.

Damage Model:

If a tower is built on each unit (you must choose exactly one tower per unit), define the following for the i-th unit (1-indexed):

• Let \(t_i = T + (\text{number of interference towers placed in units } 1 \text{ to } i-1) \times b\) be the time to traverse unit i.
• If the tower on unit i is a Laser Tower, it deals \(r \times t_i\) damage immediately.
• Regardless of the tower type on unit i, the ant suffers radiation damage during its travel on that unit equal to \((\text{number of radiation towers placed in units } 1 \text{ to } i-1) \times g \times t_i\) (since radiation effects only begin after the tower is passed).

The overall damage is the sum over all units. Formally, if you choose an ordering of towers along the path where for every unit you decide one of the three types, and if for unit i you let:

[ \text{damage}_i = \begin{cases} (r) \times t_i + (x_i \times g) \times t_i & \text{if a Laser Tower is built,}\[6mm] 0 + (x_i \times g) \times t_i & \text{if a Radiation Tower is built,}\[6mm] 0 + (x_i \times g) \times t_i & \text{if an Interference Tower is built,} \end{cases} ]

where \(x_i\) is the number of radiation towers in units \(1, 2, \ldots, i-1\) and the time \(t_i = T + (y_i \times b)\) with \(y_i\) being the number of interference towers among the first \(i-1\) units, then the total damage is:

[ \text{TotalDamage} = \sum_{i=1}^{n} \text{damage}_i. ]

Your task is to choose an assignment of towers for the \(n\) units that maximizes the total damage.

Input Format: A single line containing five space‐separated integers \(n\), \(T\), \(r\), \(g\), and \(b\).

Output Format: Output a single integer representing the maximum total damage that can be inflicted on the ants.

Note: You must deploy exactly one tower on each unit. For the purpose of analysis, assume that when a Radiation Tower or an Interference Tower is placed, its beneficial effect (damage over time or increased traversal time, respectively) applies only to subsequent units (i.e. not the current unit where it is placed).

inputFormat

The input consists of a single line with five space‐separated integers:

n T r g b

where

• \(n\) is the number of units (length of the path),
• \(T\) is the time (in seconds) to traverse one unit before any interference,
• \(r\) is the damage per second of a Laser Tower,
• \(g\) is the extra damage per second contributed by each previously built Radiation Tower,
• \(b\) is the additional time (in seconds) added per previously built Interference Tower for each unit.

outputFormat

Output a single integer: the maximum total damage that can be inflicted on the ants under an optimal tower deployment plan.

sample

5 2 3 1 1

36