#line 2 "byslib/template/bys.hpp" #ifndef LOCAL #define NDEBUG #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace bys { using std::array, std::vector, std::string, std::set, std::map, std::pair; using std::cin, std::cout, std::endl; using std::min, std::max, std::sort, std::reverse, std::abs, std::pow; // alias using ll = long long int; using ld = long double; using Pa = pair; using Vec = vector; using VecVec = std::vector; template using uset = std::unordered_set; template using umap = std::unordered_map; // const constexpr int MOD = 998244353; constexpr int INF = std::numeric_limits::max() / 2; constexpr ll LINF = std::numeric_limits::max() / 2; // I/O // pair template std::istream& operator>>(std::istream& is, std::pair& p) { return is >> p.first >> p.second; } template std::ostream& operator<<(std::ostream& os, const std::pair& p) { return os << p.first << " " << p.second; } // STL container struct is_container_impl { template static auto check(T&& obj) -> decltype(obj.begin(), obj.end(), std::true_type{}); template static auto check(...) -> std::false_type; }; template class is_container : public decltype(is_container_impl::check(std::declval())) {}; template ::value && !std::is_same::value && !std::is_same::value, std::nullptr_t>::type = nullptr> std::ostream& operator<<(std::ostream& os, const C& container) noexcept { std::for_each(std::begin(container), std::prev(std::end(container)), [&](auto e) { os << e << ' '; }); return os << *std::prev(std::end(container)); } template ::value && !std::is_same::value && !std::is_same::value, std::nullptr_t>::type = nullptr> std::istream& operator>>(std::istream& is, C& container) { std::for_each(std::begin(container), std::end(container), [&](auto&& e) { is >> e; }); return is; } // I/O helper template inline T input() { T n; cin >> n; return n; } template inline vector input(int n) { vector res(n); cin >> res; return res; } template inline std::array input() { std::array res; cin >> res; return res; } template std::tuple input() { std::tuple res; std::apply([](auto&... e) { (cin >> ... >> e); }, res); return res; } struct Print { std::ostream& os; char sep = ' ', end = '\n'; Print() : os(std::cout) {} Print(std::ostream& os) : os(os) {} ~Print() { os << std::flush; } void operator()() { os << end; } template void operator()(const T& a) { os << a << end; } template void operator()(const T& a, const Ts&... b) { os << a; (os << ... << (os << sep, b)); os << end; } } print, debug(std::cerr); // utility template inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } template inline T iceil(T a, T b) { return (a + b - 1) / b; } inline bool pop(int s, int d) { return s & (1 << d); } // config inline void init() { cin.tie(nullptr); std::ios::sync_with_stdio(false); cout << std::fixed << std::setprecision(11); std::cerr << std::boolalpha; } // macro #ifdef LOCAL #define DEBUG(...) debug("[debug] line:", __LINE__, "\n", __VA_ARGS__) #else #define DEBUG(...) #endif // clang-format off #define EXIT(...) { print(__VA_ARGS__); return; } // clang-format on // solver void solve(); void solver(int t = 1) { for (int i = 0; i < t; ++i) solve(); } } // namespace bys #line 3 "byslib/util.hpp" namespace bys { template struct ItemGetter { bool operator()(const T& lh, const T& rh) { return lh[I] < rh[I]; } }; /** * @brief 二分探索法 * https://atcoder.jp/contests/abc205/submissions/23500985 * @tparam T 初期値と返り値、is_okの第一引数 int or long long intを想定 * @param ok (T): is_okを満たす初期値 * @param ng (T): is_okを満たさない初期値 * @param is_ok (bool()): 判定用ラムダ式 * @param args... (Args...): is_okに渡される引数 可変長 * @return (T): is_okを満たす最大/小の整数 */ template T meguru_bisect(T ok, T ng, Lambda is_ok, Args... args) { assert(is_ok(ok, args...)); assert(!is_ok(ng, args...)); while (std::abs(ok - ng) > 1) { T mid = (ok + ng) / 2; if (is_ok(mid, args...)) { ok = mid; } else { ng = mid; } } return ok; } template double bisect_float(double ok, double ng, int rep, Lambda is_ok, Args... args) { assert(is_ok(ok, args...)); assert(!is_ok(ng, args...)); for (int i = 0; i < rep; i++) { double mid = (ok + ng) / 2; if (is_ok(mid, args...)) { ok = mid; } else { ng = mid; } } return ok; } template struct Compress { vector cp; Compress() {} Compress(vector& vec) : cp(vec) {} void add(T v) { cp.push_back(v); } void construct() { sort(std::begin(cp), std::end(cp)); cp.erase(std::unique(std::begin(cp), std::end(cp)), cp.end()); } int get(T v) { auto itr = std::lower_bound(std::begin(cp), std::end(cp), v); assert(*itr == v); return std::distance(cp.begin(), itr); } }; template T cumulate(vector& vec, T init = 0) { T sum = init; for (auto&& i : vec) { sum += i; i = sum; } return sum; } template T cumulate(vector& vec, BinOp op, T init = 0) { T sum = init; for (auto&& i : vec) { sum = op(sum, i); i = sum; } return sum; } struct Board { int h, w; Board(int row, int col) : h(row), w(col) {} bool contain(int row, int col) { return 0 <= row && row < h && 0 <= col && col < w; } vector> next(int i, int j, const vector> delta = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}}) { vector> res; for (auto [di, dj] : delta) { int ni = i + di; int nj = j + dj; if (contain(ni, nj)) res.push_back({ni, nj}); } return res; } int index(int i, int j) { return i * w + j; } int area() { return h * w; } }; template struct CumulativeSum { vector data; CumulativeSum(int n) : data(n + 1){}; CumulativeSum(const vector& v) : data(v.size() + 1) { std::copy(v.begin(), v.end(), std::next(data.begin())); }; void set(int i, int x) { assert(!build); data[i + 1] = x; } void construct() { assert(!build); std::partial_sum(data.begin(), data.end(), data.begin()); build = true; } // [l, r) T sum(int l, int r) { assert(build); return data[r] - data[l]; } private: bool build = false; }; template struct CumulativeSum2D { vector> data; CumulativeSum2D(int n, int m) : data(n + 1, vector(m + 1)){}; CumulativeSum2D(const vector>& v) : data(v.size() + 1, vector(v[0].size() + 1)) { int n = v.size(); for (int i = 0; i < n; ++i) { std::copy(v[i].begin(), v[i].end(), std::next(data[i + 1].begin())); } }; void set(int i, int j, int x) { assert(!build); data[i + 1][j + 1] = x; } T get(int i, int j) const { return data[i + 1][j + 1]; } void construct() { assert(!build); int n = data.size(); int m = data[0].size(); for (int i = 1; i < n; ++i) { for (int j = 1; j < m; ++j) { data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1]; } } build = true; } // [si, gi), [sj, gj) T sum(int si, int sj, int gi, int gj) { assert(build); return (data[gi][gj] - data[si][gj] - data[gi][sj] + data[si][sj]); } private: bool build = false; }; } // namespace bys #line 3 "e/e.cpp" namespace bys { void solve() { auto [n, a, b, x, y] = input(); auto h = input(n); using Data = pair; auto ok = [&](ll th) -> bool { if (th < 0) return false; ll rem_b = y * b; std::priority_queue, std::greater> que; for (int i = 0; i < n; ++i) que.push({h[i] - th, i}); for (int i = 0; i < a; ++i) { auto top = que.top(); top.first -= x; que.push(top); } vector h2; for (int i = 0; i < n; ++i) { h2.push_back(que.top()); que.pop(); } sort(h2.begin(), h2.end(), [](Data a, Data b) { return a.second < b.second; }); for (auto& [hi, id] : h2) { if (hi > 0) { if (hi > rem_b) { return false; } else { rem_b -= hi; } } } return true; }; ll ma = *std::max_element(h.begin(), h.end()); print(meguru_bisect(ma, -1LL, ok)); } } // namespace bys int main() { bys::init(); bys::solver(/* bys::input() */); return 0; }