Life Transfer
Note: “feli” is the local currency.
In the great city of Nekoresti, there are n people for which we know their ages: a[i] is the age of the i-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 k people (one driver which has to be at least
l[c]years old and k - 1 passengers). The cost to rent a car isp[c]feli.a motorcycle can transport only one person (which has to be at least
l[m]years old). The cost torent a motorcycle isp[m]feli.
Unfortunately, people have money issues, so they decided to consult Mewlin, the great local magicianfrom the city. Using a formidable spell called Mucadabra, Mewlin can transfer age from one person toanother. Formally, he can reduce the age x of a person and increase the age y of another person by the same amount (so the sum of ages is constant). The cost to transfer 1 unit of age is t feli. For magic medical reasons, the age of a person cannot be changed by more than d years (if the initial age is x, his age must be at least x - d and at most x + d at all times). Also, the age cannot go below 1 year old.
Help the people from Nekoresti to spend as little money as possible, so they can arrive in Pisiev.
Input
The first line contains two integers n and k (1 ≤ n, k ≤ 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 ≤ l[m] < l[c] ≤ 10^5, 1 ≤ p[m] < p[c] ≤ 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 t and d (0 ≤ t, d ≤ 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 n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^5) - the age of the i-th person.
Output
Print one number, the smallest amount of feli the people need to spend in order for them to reach theirdestination. If there is no such solution, print -1.