#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int inf = 1 << 30;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int nCase = 0;
int dcmp(double x) {
  if (fabs(x) < eps) return 0;
  return x < 0 ? -1 : 1;
}
inline int read() {
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  int x = 0;
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x;
}
struct Point {
  double x, y;
  Point() {}
  Point(double x, double y) {
    this->x = x;
    this->y = y;
  }
  void read() { scanf("%lf%lf", &x, &y); }
};
Point operator+(Point A, Point B) { return Point(A.x + B.x, A.y + B.y); }
Point operator-(Point A, Point B) { return Point(A.x - B.x, A.y - B.y); }
Point operator*(Point A, double p) { return Point(A.x * p, A.y * p); }
Point operator/(Point A, double p) { return Point(A.x / p, A.y / p); }
bool operator<(const Point& a, const Point& b) {
  return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool operator==(const Point& a, const Point& b) {
  return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
double Dot(Point A, Point B) { return A.x * B.x + A.y * B.y; }
double Length(Point A) { return sqrt(Dot(A, A)); }
double Angle(Point A, Point B) {
  return acos(Dot(A, B) / Length(A) / Length(B));
}
double Cross(Point A, Point B) { return A.x * B.y - A.y * B.x; }
double Area2(Point A, Point B, Point C) { return Cross(B - A, C - A); }
Point Rotate(Point A, double rad) {
  return Point(A.x * cos(rad) - A.y * sin(rad),
               A.x * sin(rad) + A.y * cos(rad));
}
bool LineCoincide(Point p1, Point p2, Point p3) {
  return dcmp(Cross(p2 - p1, p3 - p1)) == 0;
}
bool LineParallel(Point v, Point w) { return Cross(v, w) == 0; }
bool LineVertical(Point v, Point w) { return Dot(v, w) == 0; }
Point GetLineIntersection(Point P, Point v, Point Q, Point w) {
  Point u = P - Q;
  double t = Cross(w, u) / Cross(v, w);
  return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B) {
  Point v1 = B - A, v2 = P - A;
  return fabs(Cross(v1, v2)) / Length(v1);
}
double DistanceToSegment(Point P, Point A, Point B) {
  if (A == B) return Length(P - A);
  Point v1 = B - A, v2 = P - A, v3 = P - B;
  if (dcmp(Dot(v1, v2)) < 0)
    return Length(v2);
  else if (dcmp(Dot(v1, v3)) > 0)
    return Length(v3);
  else
    return fabs(Cross(v1, v2)) / Length(v1);
}
Point GetLineProjection(Point P, Point A, Point B) {
  Point v = B - A;
  return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2) {
  double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
         c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
  return dcmp(c1) * dcmp(c2) <= 0;
}
bool OnSegment(Point p, Point a1, Point a2) {
  return dcmp(Cross(a1 - p, a2 - p)) == 0 && dcmp(Dot(a1 - p, a2 - p)) < 0;
}
double PolygonArea(Point* p, int n) {
  double area = 0;
  for (int i = 1; i < n - 1; i++) area += Cross(p[i] - p[0], p[i + 1] - p[0]);
  return area / 2;
}
struct Line {
  Point a, b;
  void read() {
    a.read();
    b.read();
  }
};
const int maxn = 1234567;
int t[maxn], r[maxn], cost[maxn], nt[maxn];
int main(int argc, const char* argv[]) {
  int n, k, b, c;
  scanf("%d %d %d %d", &n, &k, &b, &c);
  b = min(b, c * 5);
  for (int i = 0; i < n; ++i) scanf("%d", t + i);
  sort(t, t + n);
  for (int i = 0; i < n; ++i) r[i] = (t[i] % 5 + 5) % 5;
  long long ans = (long long)9e18;
  for (int rot = 0; rot < 5; ++rot) {
    for (int i = 0; i < n; ++i) {
      int shift = (rot - r[i] + 5) % 5;
      cost[i] = c * shift;
      nt[i] = t[i] + shift;
    }
    long long add = 0;
    long long total = 0;
    multiset<long long> s;
    for (int i = 0; i < n; ++i) {
      if (i > 0 && nt[i] > nt[i - 1]) {
        long long value = ((nt[i] - nt[i - 1]) / 5) * 1LL * b;
        add += value;
        total += value * (long long)s.size();
      }
      s.insert(cost[i] - add);
      total += cost[i];
      while ((int)s.size() > k) {
        long long z = *(--s.end());
        total -= (z + add);
        s.erase(--s.end());
      }
      if (s.size() == k) {
        ans = min(ans, total);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

Codeforces is a wonderful platform and one its feature shows how much someone contributes to the community. Every registered user has contribution — an integer number, not necessarily positive. There are n registered users and the i-th of them has contribution ti.

Limak is a little polar bear and he's new into competitive programming. He doesn't even have an account in Codeforces but he is able to upvote existing blogs and comments. We assume that every registered user has infinitely many blogs and comments.

  * Limak can spend b minutes to read one blog and upvote it. Author's contribution will be increased by 5. 
  * Limak can spend c minutes to read one comment and upvote it. Author's contribution will be increased by 1. 



Note that it's possible that Limak reads blogs faster than comments.

Limak likes ties. He thinks it would be awesome to see a tie between at least k registered users. To make it happen he is going to spend some time on reading and upvoting. After that, there should exist an integer value x that at least k registered users have contribution exactly x.

How much time does Limak need to achieve his goal?

Input

The first line contains four integers n, k, b and c (2 ≤ k ≤ n ≤ 200 000, 1 ≤ b, c ≤ 1000) — the number of registered users, the required minimum number of users with the same contribution, time needed to read and upvote a blog, and time needed to read and upvote a comment, respectively.

The second line contains n integers t1, t2, ..., tn (|ti| ≤ 109) where ti denotes contribution of the i-th registered user.

Output

Print the minimum number of minutes Limak will spend to get a tie between at least k registered users.

Examples

Input

4 3 100 30
12 2 6 1


Output

220


Input

4 3 30 100
12 2 6 1


Output

190


Input

6 2 987 789
-8 42 -4 -65 -8 -8


Output

0

Note

In the first sample, there are 4 registered users and Limak wants a tie between at least 3 of them. Limak should behave as follows.

  * He spends 100 minutes to read one blog of the 4-th user and increase his contribution from 1 to 6. 
  * Then he spends 4·30 = 120 minutes to read four comments of the 2-nd user and increase his contribution from 2 to 6 (four times it was increaded by 1). 



In the given scenario, Limak spends 100 + 4·30 = 220 minutes and after that each of users 2, 3, 4 has contribution 6.

In the second sample, Limak needs 30 minutes to read a blog and 100 minutes to read a comment. This time he can get 3 users with contribution equal to 12 by spending 100 + 3·30 = 190 minutes:

  * Spend 2·30 = 60 minutes to read two blogs of the 1-st user to increase his contribution from 2 to 12. 
  * Spend 30 + 100 minutes to read one blog and one comment of the 3-rd user. His contribution will change from 6 to 6 + 5 + 1 = 12. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int inf = 1 << 30;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int nCase = 0;
int dcmp(double x) {
  if (fabs(x) < eps) return 0;
  return x < 0 ? -1 : 1;
}
inline int read() {
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  int x = 0;
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x;
}
struct Point {
  double x, y;
  Point() {}
  Point(double x, double y) {
    this->x = x;
    this->y = y;
  }
  void read() { scanf("%lf%lf", &x, &y); }
};
Point operator+(Point A, Point B) { return Point(A.x + B.x, A.y + B.y); }
Point operator-(Point A, Point B) { return Point(A.x - B.x, A.y - B.y); }
Point operator*(Point A, double p) { return Point(A.x * p, A.y * p); }
Point operator/(Point A, double p) { return Point(A.x / p, A.y / p); }
bool operator<(const Point& a, const Point& b) {
  return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool operator==(const Point& a, const Point& b) {
  return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
double Dot(Point A, Point B) { return A.x * B.x + A.y * B.y; }
double Length(Point A) { return sqrt(Dot(A, A)); }
double Angle(Point A, Point B) {
  return acos(Dot(A, B) / Length(A) / Length(B));
}
double Cross(Point A, Point B) { return A.x * B.y - A.y * B.x; }
double Area2(Point A, Point B, Point C) { return Cross(B - A, C - A); }
Point Rotate(Point A, double rad) {
  return Point(A.x * cos(rad) - A.y * sin(rad),
               A.x * sin(rad) + A.y * cos(rad));
}
bool LineCoincide(Point p1, Point p2, Point p3) {
  return dcmp(Cross(p2 - p1, p3 - p1)) == 0;
}
bool LineParallel(Point v, Point w) { return Cross(v, w) == 0; }
bool LineVertical(Point v, Point w) { return Dot(v, w) == 0; }
Point GetLineIntersection(Point P, Point v, Point Q, Point w) {
  Point u = P - Q;
  double t = Cross(w, u) / Cross(v, w);
  return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B) {
  Point v1 = B - A, v2 = P - A;
  return fabs(Cross(v1, v2)) / Length(v1);
}
double DistanceToSegment(Point P, Point A, Point B) {
  if (A == B) return Length(P - A);
  Point v1 = B - A, v2 = P - A, v3 = P - B;
  if (dcmp(Dot(v1, v2)) < 0)
    return Length(v2);
  else if (dcmp(Dot(v1, v3)) > 0)
    return Length(v3);
  else
    return fabs(Cross(v1, v2)) / Length(v1);
}
Point GetLineProjection(Point P, Point A, Point B) {
  Point v = B - A;
  return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2) {
  double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
         c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
  return dcmp(c1) * dcmp(c2) <= 0;
}
bool OnSegment(Point p, Point a1, Point a2) {
  return dcmp(Cross(a1 - p, a2 - p)) == 0 && dcmp(Dot(a1 - p, a2 - p)) < 0;
}
double PolygonArea(Point* p, int n) {
  double area = 0;
  for (int i = 1; i < n - 1; i++) area += Cross(p[i] - p[0], p[i + 1] - p[0]);
  return area / 2;
}
struct Line {
  Point a, b;
  void read() {
    a.read();
    b.read();
  }
};
const int maxn = 1234567;
int t[maxn], r[maxn], cost[maxn], nt[maxn];
int main(int argc, const char* argv[]) {
  int n, k, b, c;
  scanf("%d %d %d %d", &n, &k, &b, &c);
  b = min(b, c * 5);
  for (int i = 0; i < n; ++i) scanf("%d", t + i);
  sort(t, t + n);
  for (int i = 0; i < n; ++i) r[i] = (t[i] % 5 + 5) % 5;
  long long ans = (long long)9e18;
  for (int rot = 0; rot < 5; ++rot) {
    for (int i = 0; i < n; ++i) {
      int shift = (rot - r[i] + 5) % 5;
      cost[i] = c * shift;
      nt[i] = t[i] + shift;
    }
    long long add = 0;
    long long total = 0;
    multiset<long long> s;
    for (int i = 0; i < n; ++i) {
      if (i > 0 && nt[i] > nt[i - 1]) {
        long long value = ((nt[i] - nt[i - 1]) / 5) * 1LL * b;
        add += value;
        total += value * (long long)s.size();
      }
      s.insert(cost[i] - add);
      total += cost[i];
      while ((int)s.size() > k) {
        long long z = *(--s.end());
        total -= (z + add);
        s.erase(--s.end());
      }
      if (s.size() == k) {
        ans = min(ans, total);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

```