Minimizing Goods Value Loss in Factory Logistics

There are n factories located on the road between point A and point B. The factory i is located a_i kilometers away from A. A processing plant is located at B, which is x kilometers from A. Each factory produces b_i goods, and every good in factory i is produced at time p_i minutes after the rain begins.

Because of heavy rain, every good loses value as soon as it is produced: for every minute a good is stored (either in the factory’s warehouse or in Small I’s backpack) before reaching the processing plant, its value decreases by m monetary units. Small I transports the goods by repeatedly making round trips from A to B and back. His walking speed is 1 kilometer per minute. On each trip, while going from A to B, he collects all goods that have been produced by the factories he passes. He does not pick up goods on the return trip from B to A.

Initially, Small I has a stamina of c. Every kilometer walked (in any direction) reduces his stamina by 1. Moreover, after every departure he is allowed to create at most one clone (a split of himself) that will make a trip following the same rules. However, note that all clones (and the original) share the same stamina pool. It must always be ensured that at any moment each person in the field has enough stamina left to return to A — that is, if a person is at distance p from A, the remaining shared stamina must be at least p.

To plan his trips, Small I may even start his journey at a negative time (i.e. before the rain starts) so as to minimize the time goods spend waiting. Suppose that on a trip he departs from A at time d. Then he will pass a factory located at distance a_i at time d + a_i, but if d + a_i is earlier than p_i, he must wait until time p_i for the goods to be produced. In other words, the pickup time for factory i on that trip is max(d + a_i, p_i) and the waiting time is max(d + a_i - p_i, 0).

It can be shown that when collecting goods from a contiguous set of factories (after sorting them by their distance from A), the optimal departure time is

[ d = \max_{i \in \text{segment}} (p_i - a_i) ]

Under this choice the loss incurred by factory i in the segment is

[ \text{loss}i = m\cdot\Big(\max{j \in \text{segment}}(p_j - a_j) + a_i - p_i\Big) \times b_i. ]

The total loss is the sum of these losses. Small I is allowed to make at most T trips, where

[ T = \left\lfloor \frac{c}{2x} \right\rfloor, ]

since each round trip (from A to B and back) costs 2x stamina. Your task is to partition the sorted factories into at most T segments (each segment corresponding to one trip) so as to minimize the overall loss. Output this minimum total loss.

inputFormat

The first line contains five integers: n, x, c, k, and m — the number of factories, the distance from A to B, the initial stamina, the number of minutes the rain has already been falling, and the loss in value per minute per good, respectively.

The second line contains n integers: a₁, a₂, ..., aₙ where a_i is the distance from A to factory i.

The third line contains n integers: b₁, b₂, ..., bₙ where b_i is the number of goods produced by factory i.

The fourth line contains n integers: p₁, p₂, ..., pₙ where p_i is the production time (in minutes after the rain begins) for the goods of factory i.

outputFormat

Output a single integer representing the minimum total loss (in value units) that can be achieved by an optimal plan of trips.

sample

3 10 40 5 2
1 5 9
10 20 30
0 3 10

40