_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:
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.
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 second line contains $n$ integers $a_1, a_2, \\dots, a_n$ ($1 <= a_i <= 10^5$) — the age of the $i$-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 $-1$.
## 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 second line contains $n$ integers $a_1, a_2, \\dots, 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 their destination. If there is no such solution, print $-1$.
[samples]
**Definitions**
Let $ x \in \mathbb{Z}^+ $ be the required amount of gold.
Let $ n \in \mathbb{Z}^+ $ be the number of houses.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers representing gold in each house, indexed from 1 to $ n $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq x \leq 10^9 $
3. $ 1 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Find the minimum distance $ d $ Bashar must walk, defined as the number of edges between the first and last house visited (i.e., if he visits houses from index $ l $ to $ r $, then $ d = r - l $), such that the sum of gold from a contiguous subarray $ \sum_{i=l}^{r} a_i \geq x $.
If no such contiguous subarray exists, output $ -1 $.
Formally, compute:
$$
\min_{1 \leq l \leq r \leq n} \{ r - l \mid \sum_{i=l}^{r} a_i \geq x \}
$$
If the minimum does not exist, output $ -1 $.