문제

The administrators of algospot.com. are busy preparing yet another programming contest. They have selected N$N$ problems from the problem pool that will appear in the next contest.

Unfortunately, at this time, only one of the administrators, the Lord of the Tremendously Dazzling and Terrific Land, is able to typeset the problems. Because typesetting requires a lot of concentration, the administrator may process one problem at a time. Yet she may freely choose the order of the problems to typeset. Each problem requires a different amount of time of typesetting. Let us denote the required typesetting time for the i$i$-th problem as T_i.$T_i.$

The director of the contest is going to set a deadline for typesetting. As a result, the typesetter, LTDTL will feel some sort of uneasiness. Let us consider the following model for measuring uneasiness, given the non-negative deadline D$D$:

where A, B$A, B$ and C$C$ are non-negative integer constants.

Before defining tardiness and earliness, let us take a close look at the first term. A \cdot D$A \cdot D$ represents the psychological pressure due to the late deadline. Although it appears to the typesetter that she has more time to typeset the problems, it also means that the typesetter will be occupied by all the hectic work for a longer period of time, and thus she will be feeling uneasy for a long time. Hence, the further the deadline is from now, the more uneasy the typesetter will feel.

\mathrm{Tardiness}_i$\mathrm{Tardiness}_i$ means the 'lateness' of the i$i$-th problem. \mathrm{Tardiness}_i$\mathrm{Tardiness}_i$ is zero if the typesetting for the i$i$-th problem will be done no later than the deadline. Otherwise, it will be defined as the difference between the finish time of the i$i$-th problem and the deadline.

Analogously, \mathrm{Earliness}_i$\mathrm{Earliness}_i$ is zero if the typesetting of the i$i$-th problem is done later than the deadline. Otherwise, it will be defined as the difference between the finish time of the i$i$-th problem and the deadline.

For example, if we assume D = 5$D = 5$ and the finish time of the problem is 7$7$, then the uneasiness value for that problem will be A\cdot 5 + B \cdot 2 + C \cdot 0$A\cdot 5 + B \cdot 2 + C \cdot 0$.

The minimum amount of the uneasiness will be dependent on the deadline and the order of typesetting problems. Write a program that finds the minimum amount of uneasiness.