Minimum Travel Cost with Age Transfer

In the metropolis Nekoresti, there are n people with known ages. The i-th person has age \(a_i\). They are on vacation and want to visit the famous museum Koshkseum in Pisiev. They can travel via one of two vehicle types:

• A car that can carry k people (one driver and k - 1 passengers). The driver must be at least \(l_c\) years old and the rental cost for one car is \(p_c\) feli.
• A motorcycle that carries exactly 1 person who must be at least \(l_m\) years old. The rental cost for one motorcycle is \(p_m\) feli.

Not having a lot of money, the group seeks help from the local wizard Mewlin. Using his powerful magic Mucadabra, he can transfer age among persons. Formally, he can decrease one person’s age while increasing another’s by the same amount (so the total age remains unchanged). Transferring 1 year of age costs \(t\) feli. However, no person’s age can be altered by more than \(d\) years, meaning that if someone’s original age is \(x\), their final age must lie in \( [x-d, x+d] \) (and ages can never drop below 1).

Your task is to help them achieve a valid assignment of vehicles (choosing some people as drivers, possibly boosting their ages via magic) so that all \(n\) people can travel, while minimizing the total cost. The total cost includes vehicle rental costs plus the total magic cost (which is \(t \times\) the total number of age years transferred). If it is impossible to form a valid assignment even after using magic under the given limitations, output -1.

Note: When using magic, the increase needed for a driver is \(\max(0, r - a_i)\) (where \(r\) is the required minimum age for that role). However, age can only be increased by at most \(d\) (i.e. if \(r - a_i > d\), the person is ineligible for that role). Also, any person not used as a driver (a passenger) can donate age by decreasing their age (up to \(d\) years or until their age hits 1, whichever is less). Similarly, even a qualified driver may donate extra age provided they still meet the minimum required for their role after donating.

inputFormat

The first line contains eight integers: \(n\), \(k\), \(p_c\), \(p_m\), \(l_c\), \(l_m\), \(t\), and \(d\) — representing the number of people, car capacity, car rental cost, motorcycle rental cost, minimum age for a car driver, minimum age for a motorcycle driver, cost per year of age transfer, and maximum allowed age change per person, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), where \(a_i\) is the age of the \(i\)-th person.

outputFormat

Output a single integer: the minimum total cost (vehicle rental cost plus magic cost) required to transport all people. If it is impossible to meet the requirements, output -1.

sample

5 4 100 30 18 16 2 5
16 15 15 18 17

130