E. Life Transfer
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 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 $$$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 \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 \lt l_c \leq 10^5$$$, $$$1 \leq p_m \lt 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 $$$t$$$ and $$$d$$$ ($$$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 second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 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 their destination. If there is no such solution, print $$$-1$$$.

Examples
Input
2 2
18 1000 16 1
5 3
16 15
Output
1010
Input
2 2
23 10 15 5
2 2
9 20
Output
-1