#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #pragma warning(disable:4996) typedef long long ll; typedef unsigned long long ull; #define MIN(a, b) ((a)>(b)? (b): (a)) #define MAX(a, b) ((a)<(b)? (b): (a)) #define LINF 9223300000000000000 #define LINF2 1223300000000000000 #define LINF3 1000000000000 #define INF 2140000000 const long long MOD = 1000000007; //const long long MOD = 998244353; using namespace std; class bigint { private: //static const int BASE = 1000, LEN = 3; static const int BASE = 100000000, LEN = 8; bool negative; std::vector a; bigint& normalize(); public: bigint(int x = 0); bigint(const std::string& s); bigint& operator = (const bigint& x); bigint& operator = (int x); bigint& operator = (const std::string& s); const bool operator < (const bigint& x) const; const bool operator > (const bigint& x) const; const bool operator <= (const bigint& x) const; const bool operator >= (const bigint& x) const; const bool operator != (const bigint& x) const; const bool operator == (const bigint& x) const; bigint operator -() const; bigint& operator += (const bigint& x); bigint& operator -= (const bigint& x); bigint& operator *= (const bigint& x); bigint& operator /= (const bigint& x); bigint& operator %= (const bigint& x); const bigint operator + (const bigint& x) const; const bigint operator - (const bigint& x) const; const bigint operator * (const bigint& x) const; const bigint operator / (const bigint& x) const; const bigint operator % (const bigint& x) const; friend std::pair divmod(const bigint& lhs, const bigint& rhs); friend const bigint abs(bigint x); static string tostr( const bigint& x); }; bigint& bigint::normalize() { int i = a.size()-1; while (i >= 0 && a[i] == 0) --i; a.resize(i+1); if (a.size() == 0) negative = false; return *this; } bigint::bigint(int x) : negative(x<0) { x = abs(x); for (; x > 0; x /= BASE) a.push_back(x % BASE); } bigint::bigint(const std::string& s): negative(false) { int p = 0; if (s[p] == '-') { ++p; negative = true; } else if (s[p] == '+') { ++p; } for (int i = s.size()-1, v = BASE; i >= p; --i, v*=10) { int x = s[i]-'0'; if (x < 0 || 9 < x) { printf("error: parse error:%s\n", s.c_str()); exit(1); } if (v == BASE) { v = 1; a.push_back(x); } else a.back() += (x)*v; } normalize(); } bigint& bigint::operator = (const bigint& x) { negative = x.negative; a = x.a; return *this; } bigint& bigint::operator = (int x) { return *this = bigint(x); } bigint& bigint::operator = (const std::string& s) { return *this = bigint(s); } const bool bigint::operator < (const bigint& x) const { if (negative != x.negative) return negative < x.negative; if (a.size() != x.a.size()) return (a.size() < x.a.size())^negative; for(int i = a.size()-1; i >= 0; --i) if (a[i] != x.a[i]) return (a[i] < x.a[i])^negative; return false; } const bool bigint::operator > (const bigint& x) const { return x<(*this); } const bool bigint::operator <= (const bigint& x) const { return !(x<(*this)); } const bool bigint::operator >= (const bigint& x) const { return !((*this) b(x.a); if ((*this < x) ^ negative) { a.swap(b); negative = !negative; } for (int i = 0, tmp = 0; i < (int)a.size(); ++i) { a[i] += BASE - (i<(int)b.size()?b[i]:0) + tmp; tmp = a[i] / BASE - 1; a[i] %= BASE; } return this->normalize(); } bigint& bigint::operator *= (const bigint& x) { negative ^= x.negative; std::vector c(a.size()*x.a.size()+1); for (int i = 0; i < (int)a.size(); ++i) { long long tmp = 0; for (int j = 0; j < (int)x.a.size(); ++j) { long long v = (long long)a[i] * x.a[j] + c[i+j] + tmp; tmp = v / BASE; c[i+j] = (int)(v % BASE); } if (tmp) c[i+x.a.size()] += (int)tmp; } a.swap(c); return this->normalize(); } bigint& bigint::operator /= (const bigint& x) { return *this = divmod(*this,x).first; } bigint& bigint::operator %= (const bigint& x) { return *this = divmod(*this,x).second; } const bigint bigint::operator + (const bigint& x) const { bigint res(*this); return res += x; } const bigint bigint::operator - (const bigint& x) const { bigint res(*this); return res -= x; } const bigint bigint::operator * (const bigint& x) const { bigint res(*this); return res *= x; } const bigint bigint::operator / (const bigint& x) const { bigint res(*this); return res /= x; } const bigint bigint::operator % (const bigint& x) const { bigint res(*this); return res %= x; } std::pair divmod(const bigint& lhs, const bigint& rhs) { if (!rhs.a.size()) { printf("error: division by zero\n"); exit(1); } bigint x(abs(rhs)), q, r; for (int i = lhs.a.size()-1; i >= 0; --i) { r = r * bigint::BASE + lhs.a[i]; int head = 0, tail = bigint::BASE; if (r >= x) { while (head + 1 < tail) { int mid = (head + tail) / 2; if (x * bigint(mid) > r) tail = mid; else head = mid; } r -= x * head; } q.a.push_back(head); } reverse(q.a.begin(), q.a.end()); bool neg = lhs.negative ^ lhs.negative; q.negative = neg; r.negative = neg; return std::make_pair(q.normalize(), r.normalize()); } const bigint abs(bigint x) { x.negative = false; return x; } string bigint::tostr( const bigint& x) { string a; if (x.negative) a += "-"; if (!x.a.size()) a += "0"; else a += to_string((long long)x.a.back()); for (int i=x.a.size()-2; i>=0; --i) { char tmp[bigint::LEN+1]={0}; sprintf(tmp, "%0*d", bigint::LEN, x.a[i]); a += string(tmp); } return a; } bigint gcd(bigint a, bigint b) { if(b == 0) return a; return gcd(b,a%b); } #define PRINT(x) printf("%s\n", bigint::tostr(x).c_str()); /* int main() { char stra[105]={0}; char strb[105]={0}; scanf("%s", &stra); scanf("%s", &strb); bigint a(stra); bigint b(strb); PRINT(a); PRINT(b); PRINT(-a); PRINT(-b); PRINT(abs(a)); PRINT(abs(b)); PRINT(ab); PRINT(a<=b); PRINT(a>=b); PRINT(a!=b); PRINT(a==b); PRINT(a+b); PRINT(a-b); PRINT(a*b); PRINT(a/b); PRINT(a%b); return 0; } */ void solve() { int n, K, x, y; scanf("%d%d%d%d", &n, &K, &x, &y); vector a(n); int i; for (i = 0; i < n; i++) { int tmp; scanf("%d", &tmp); int tmp2=(tmp - 1) / K; if ((tmp - 1) % K) tmp2++; a[i] = tmp2; } sort(a.rbegin(), a.rend()); vector s(n + 1); for (i = 0; i < n; i++) { s[i + 1] = s[i] + (bigint)a[i]; } bigint ans = bigint(s[n]) * bigint(x); for (i = 0; i < n; i++) { bigint ans0 = (bigint)(s[i + 1] - (bigint)(i+1)*(bigint)a[i])*(bigint)x; ans0 = ans0 + (bigint)y*(bigint)a[i]; bigint diff = ans - ans0; if (abs(diff) == diff) { ans = ans0; } } PRINT(ans); return; } int main(int argc, char* argv[]) { #if 1 solve(); #else int T; scanf("%d", &T); int t; for(t=0; t