P5800 [SEERC 2019] Life Transfer

*Note: “feli” is the local currency unit.*

In the metropolis Nekoresti, there are $n$ people with known ages. The age of the $i$-th person is $a_i$. They are enjoying their vacation, so they decide to visit Pisiev to tour a famous museum called Koshkseum. They can travel either by car or by motorcycle: - A **car** can carry up to $k$ people (including one driver whose age is at least $l_c$, and up to $k-1$ passengers). The rental cost of one car is $p_c$ feli. - A **motorcycle** can carry only $1$ person (whose age is at least $l_m$). The rental cost of one motorcycle is $p_m$ feli. Unfortunately, these people are not very wealthy, so they ask a local archmage, Mewlin, to help them. By using a powerful spell, Mucadabra, Mewlin can transfer people’s ages. Formally, he can decrease the age of a person with age $x$, while increasing the age of a person with age $y$ by the same amount (so the sum of the two ages stays unchanged). The cost to transfer $1$ year of age is $t$ feli. Due to the limits of the spell, the spell cannot change a person’s age by more than $d$ (if a person’s age is $x$, then the changed age can only be within $[x-d, x+d]$). Also, an age cannot be less than $1$. Help them spend the least amount of money to travel from Nekoresti to Pisiev.

The first line contains two integers $n$ and $k$ $(1 \leq n, k \leq 10^5)$, representing the number of people traveling and the maximum capacity of one car. The second line contains four integers $l_c, p_c, l_m$ and $p_m$ $(1 \leq l_m < l_c \leq 10^5, 1 \leq p_m < p_c \leq 10^5)$, representing the minimum age to drive, the rental cost of one car, the minimum age to ride a motorcycle, and the rental cost of one motorcycle. The third line contains two integers $t$ and $d$ $(0 \leq t, d \leq 10^5)$, representing the cost to transfer $1$ year of age and the limit $d$ on how much the spell can change an age. The fourth line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 10^5)$, where $a_i$ is the age of the $i$-th person.

Output one number, the minimum total cost to get everyone to the destination. If there is no solution, output $-1$.

Translated by ChatGPT 5