Problem Description

In the metropolis of Nekoresti, there are $n$ people with known ages, where the $i$-th person is $a_i$ years old. Enjoying their vacation, they decided to visit the famous museum Koshkseum in Pisiev. They can travel by car or motorcycle:

• A car can carry $k$ people (including a driver who is at least $l_c$ years old and $k-1$ passengers). The rental fee for a car is $p_c$ feli.
• A motorcycle can only carry one person (who is at least $l_m$ years old). The rental fee for a motorcycle is $p_m$ feli.

Unfortunately, these people are not very wealthy, so they asked a local powerful wizard, Mewlin, for help. Using a strong magic called Mucadabra, Mewlin can transfer people's ages. Formally, he can reduce the age of a person aged $x$ by some amount and increase the age of another person aged $y$ by the same amount (the total age of these two people remains unchanged). The cost to transfer one year of age is $t$ feli. Due to the limitations of the magic, the age of a person cannot be changed by more than $d$ (if a person's age is $x$, the new age must be within the range $[x-d, x+d]$). Also, the age cannot be less than 1 year.

Help these people spend the least amount of money to travel from Nekoresti to Pisiev.

Input Format

The first line contains two integers $n$ and $k$ $(1 \leq n, k \leq 10^5)$, representing the number of people and the maximum capacity of a car.

The second line contains four integers $l_c, p_c, l_m, 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 a car, the rental fee for a car, the minimum age to ride a motorcycle, and the rental fee for a motorcycle.

The third line contains two integers $t$ and $d$ $(0 \leq t, d \leq 10^5)$, representing the cost to transfer one year of age and the limit of age change by the magic.

The fourth line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 10^5)$, where $a_i$ represents the age of the $i$-th person.

Output Format

Output a single number, which is the minimum cost for everyone to reach the destination. If it is not possible, output $-1$.

Sample Input and Output

Sample Input #1

2 2
18 1000 16 1
5 3
16 15

Sample Output #1

1010

Sample Input #2

2 2
23 10 15 5
2 2
9 20

Sample Output #2

-1

见题面 Input 部分

见题面 Output 部分