나이 옮기기

참고: “feli”는 현지 화폐 단위이다.

위대한 도시 Nekoresti에는 나이를 알고 있는 사람이 $n$명 있다. $a_i$는 $i$번째 사람의 나이이다. 지금 이들은 휴가 중이며, Pisiev로 여행을 떠나 유명한 박물관 Koshkseum을 방문하기로 했다. 이동 수단은 자동차 또는 오토바이 중에서 고를 수 있다.

• 자동차는 $k$명을 태울 수 있다. 운전자는 최소 $l_c$살 이상이어야 하고, 나머지 $k-1$명은 승객이다. 자동차 대여 비용은 $p_c$ feli이다.
• 오토바이는 한 명만 태울 수 있다. 탑승자는 최소 $l_m$살 이상이어야 한다. 오토바이 대여 비용은 $p_m$ feli이다.

안타깝게도 이들은 돈이 부족하다. 그래서 이 도시의 위대한 마법사 Mewlin에게 도움을 청하기로 했다. Mewlin은 Mucadabra라는 강력한 주문으로 한 사람의 나이를 다른 사람에게 옮길 수 있다. 정확히는 한 사람의 나이 $x$를 줄이고 다른 사람의 나이 $y$를 같은 양만큼 늘린다. 따라서 나이의 총합은 변하지 않는다. 나이 1년을 옮기는 데 $t$ feli가 든다. 의학적인 이유로 한 사람의 나이는 원래 나이에서 $d$년을 넘게 바뀔 수 없다. 즉 처음 나이가 $x$이면 언제나 $x-d$ 이상 $x+d$ 이하여야 한다. 또한 나이는 1살 아래로 내려갈 수 없다.

Nekoresti 사람들이 Pisiev에 도착하는 데 돈을 최대한 적게 쓰도록 도와라.

첫 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le n, k \le 10^5$). $n$은 사람 수이고, $k$는 한 대의 자동차에 탈 수 있는 최대 인원이다.

둘째 줄에 네 정수 $l_c$, $p_c$, $l_m$, $p_m$이 주어진다 ($1 \le l_m < l_c \le 10^5$, $1 \le p_m < p_c \le 10^5$). $l_c$는 자동차를 운전하는 데 필요한 최소 나이, $p_c$는 자동차 대여 비용, $l_m$은 오토바이를 운전하는 데 필요한 최소 나이, $p_m$은 오토바이 대여 비용이다.

셋째 줄에 두 정수 $t$와 $d$가 주어진다 ($0 \le t, d \le 10^5$). $t$는 나이 1년을 옮기는 비용이고, $d$는 각 사람에게 주문을 적용할 수 있는 최대 횟수이다.

넷째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^5$). $a_i$는 $i$번째 사람의 나이이다.

Pisiev에 도착하는 데 드는 최소 비용을 한 정수로 출력한다. 그러한 방법이 없으면 $-1$을 출력한다.