{"raw_statement":[{"iden":"statement","content":"_Note: \"feli\" is the local currency._\n\nIn 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:\n\nUnfortunately, 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.\n\nHelp the people from Nekoresti to spend as little money as possible, so they can arrive in Pisiev.\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nThe second line contains $n$ integers $a_1, a_2, \\\\dots, a_n$ ($1 <= a_i <= 10^5$) — the age of the $i$-th person.\n\nPrint 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$.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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$."},{"iden":"examples","content":"Input2 2\n18 1000 16 1\n5 3\n16 15\nOutput1010\nInput2 2\n23 10 15 5\n2 2\n9 20\nOutput-1\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ x \\in \\mathbb{Z}^+ $ be the required amount of gold.  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of houses.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing gold in each house, indexed from 1 to $ n $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq x \\leq 10^9 $  \n3. $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFind 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 $.  \n\nIf no such contiguous subarray exists, output $ -1 $.  \n\nFormally, compute:  \n$$\n\\min_{1 \\leq l \\leq r \\leq n} \\{ r - l \\mid \\sum_{i=l}^{r} a_i \\geq x \\}\n$$  \nIf the minimum does not exist, output $ -1 $.","simple_statement":"Bashar needs x gold coins. There are n houses in a line, each with a_i coins. He can start and stop at any house. Find the minimum number of houses he must walk through (i.e., the length of the shortest contiguous subarray) to collect at least x coins. If impossible, print -1.","has_page_source":false}