Life Transfer#11278
Note: "feli" is the local currency.
In the great city of Nekoresti, there are people for which we know their ages: a_i is the age of the -th person. Currently, they are on vacation, so they decided to go on a trip to Pisiev to visit a Koshkseum, a famous museum. They can go either by car or by motorcycle:
a car can transport people (one driver which has to be at least l_c years old and k - 1 passengers). The cost to rent a car is p_c feli.
a motorcycle can transport only one person (which has to be at least l_m years old). The cost to rent a motorcycle is p_m feli.
Unfortunately, people have money issues, so they decided to consult Mewlin, the great local magician from the city. Using a formidable spell called Mucadabra, Mewlin can transfer age from one person to another. Formally, he can reduce the age of a person and increase the age of another person by the same amount (so the sum of ages is constant). The cost to transfer unit of age is feli. For magic medical reasons, the age of a person cannot be changed by more than years (if the initial age is , his age must be at least x - d and at most x + d at all times). Also, the age cannot go below year old.
Help the people from Nekoresti to spend as little money as possible, so they can arrive in Pisiev.
The first line contains two integers and (1 \leq n, k \leq 10^5) - the number of people and the maximum number of people that can be in 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) - the minimum needed age to drive a car; the price of renting one car; the minimum needed age to drive a motorcycle and the price of renting one motorcycle.
The third line contains two integers and (0 \leq t, d \leq 10^5) - the price of transferring one year and the maximum number of times the spells can be applied per each person.
The fourth line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^5) - the age of the -th person.
Print one number, the smallest amount of feli the people need to spend in order for them to reach their destination. If there is no such solution, print .
Example 1
Example 2