#include namespace suisen { template bool chmin(T& x, const T& y) { return y >= x ? false : (x = y, true); } template bool chmax(T& x, const T& y) { return y <= x ? false : (x = y, true); } template constexpr int pow_m1(T n) { return -(n & 1) | 1; } template constexpr T fld(const T x, const T y) { T q = x / y, r = x % y; return q - ((x ^ y) < 0 and (r != 0)); } template constexpr T cld(const T x, const T y) { T q = x / y, r = x % y; return q + ((x ^ y) > 0 and (r != 0)); } } namespace suisen::macro { #define IMPL_REPITER(cond) auto& begin() { return *this; } auto end() { return nullptr; } auto& operator*() { return _val; } auto& operator++() { return _val += _step, *this; } bool operator!=(std::nullptr_t) { return cond; } template == std::is_signed_v), std::nullptr_t> = nullptr> struct rep_impl { Int _val; const Int _end, _step; rep_impl(Int n) : rep_impl(0, n) {} rep_impl(IntL l, Int r, IntStep step = 1) : _val(l), _end(r), _step(step) {} IMPL_REPITER((_val < _end)) }; template == std::is_signed_v), std::nullptr_t> = nullptr> struct rrep_impl { Int _val; const Int _end, _step; rrep_impl(Int n) : rrep_impl(0, n) {} rrep_impl(IntL l, Int r) : _val(r - 1), _end(l), _step(-1) {} rrep_impl(IntL l, Int r, IntStep step) : _val(l + fld(r - l - 1, step) * step), _end(l), _step(-step) {} IMPL_REPITER((_val >= _end)) }; template struct repinf_impl { Int _val; const Int _step; repinf_impl(Int l, IntStep step = 1) : _val(l), _step(step) {} IMPL_REPITER((true)) }; #undef IMPL_REPITER } #include #include #include namespace suisen { template using constraints_t = std::enable_if_t, std::nullptr_t>; template struct bitnum { static constexpr int value = 0; }; template struct bitnum>> { static constexpr int value = std::numeric_limits>::digits; }; template static constexpr int bitnum_v = bitnum::value; template struct is_nbit { static constexpr bool value = bitnum_v == n; }; template static constexpr bool is_nbit_v = is_nbit::value; template struct safely_multipliable { using type = T; }; template struct safely_multipliable, is_nbit>> { using type = long long; }; template struct safely_multipliable, is_nbit>> { using type = __int128_t; }; template struct safely_multipliable, is_nbit>> { using type = unsigned long long; }; template struct safely_multipliable, is_nbit>> { using type = __uint128_t; }; template using safely_multipliable_t = typename safely_multipliable::type; template struct rec_value_type { using type = T; }; template struct rec_value_type> { using type = typename rec_value_type::type; }; template using rec_value_type_t = typename rec_value_type::type; template class is_iterable { template static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval()))::value; }; template static constexpr bool is_iterable_v = is_iterable::value; template class is_writable { template static auto test(T_ e) -> decltype(std::declval() << e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval()))::value; }; template static constexpr bool is_writable_v = is_writable::value; template class is_readable { template static auto test(T_ e) -> decltype(std::declval() >> e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval()))::value; }; template static constexpr bool is_readable_v = is_readable::value; } // namespace suisen namespace suisen::io { template >, std::negation>>>, std::nullptr_t> = nullptr> struct InputStream { private: using istream_type = std::remove_reference_t; IStream is; struct { InputStream* is; template operator T() { T e; *is >> e; return e; } } _reader{ this }; public: template InputStream(IStream_ &&is) : is(std::move(is)) {} template InputStream(IStream_ &is) : is(is) {} template InputStream& operator>>(T& e) { if constexpr (suisen::is_readable_v) is >> e; else _read(e); return *this; } auto read() { return _reader; } template void read(Head& head, Tail &...tails) { ((*this >> head) >> ... >> tails); } istream_type& get_stream() { return is; } private: static __uint128_t _stou128(const std::string& s) { __uint128_t ret = 0; for (char c : s) if ('0' <= c and c <= '9') ret = 10 * ret + c - '0'; return ret; } static __int128_t _stoi128(const std::string& s) { return (s[0] == '-' ? -1 : +1) * _stou128(s); } void _read(__uint128_t& v) { v = _stou128(std::string(_reader)); } void _read(__int128_t& v) { v = _stoi128(std::string(_reader)); } template void _read(std::pair& a) { *this >> a.first >> a.second; } template void _read(std::tuple& a) { if constexpr (N < sizeof...(Args)) *this >> std::get(a), _read(a); } template , std::nullptr_t> = nullptr> void _read(Iterable& a) { for (auto& e : a) *this >> e; } }; template InputStream(IStream &&) -> InputStream; template InputStream(IStream &) -> InputStream; InputStream cin{ std::cin }; auto read() { return cin.read(); } template void read(Head& head, Tail &...tails) { cin.read(head, tails...); } } // namespace suisen::io namespace suisen { using io::read; } // namespace suisen namespace suisen::io { template >, std::negation>>>, std::nullptr_t> = nullptr> struct OutputStream { private: using ostream_type = std::remove_reference_t; OStream os; public: template OutputStream(OStream_ &&os) : os(std::move(os)) {} template OutputStream(OStream_ &os) : os(os) {} template OutputStream& operator<<(const T& e) { if constexpr (suisen::is_writable_v) os << e; else _print(e); return *this; } void print() { *this << '\n'; } template void print(const Head& head, const Tail &...tails) { *this << head, ((*this << ' ' << tails), ...), *this << '\n'; } template , std::nullptr_t> = nullptr> void print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") { for (auto it = v.begin(); it != v.end();) if (*this << *it; ++it != v.end()) *this << sep; *this << end; } ostream_type& get_stream() { return os; } private: void _print(__uint128_t value) { char buffer[41], *d = std::end(buffer); do *--d = '0' + (value % 10), value /= 10; while (value); os.rdbuf()->sputn(d, std::end(buffer) - d); } void _print(__int128_t value) { if (value < 0) *this << '-'; _print(__uint128_t(value < 0 ? -value : value)); } template void _print(const std::pair& a) { *this << a.first << ' ' << a.second; } template void _print(const std::tuple& a) { if constexpr (N < std::tuple_size_v>) { if constexpr (N) *this << ' '; *this << std::get(a), _print(a); } } template , std::nullptr_t> = nullptr> void _print(const Iterable& a) { print_all(a, " ", ""); } }; template OutputStream(OStream_ &&) -> OutputStream; template OutputStream(OStream_ &) -> OutputStream; OutputStream cout{ std::cout }, cerr{ std::cerr }; template void print(const Args &... args) { cout.print(args...); } template , std::nullptr_t> = nullptr> void print_all(const Iterable& v, const std::string& sep = " ", const std::string& end = "\n") { cout.print_all(v, sep, end); } } // namespace suisen::io namespace suisen { using io::print, io::print_all; } // namespace suisen namespace suisen { template , std::enable_if_t, std::is_invocable_r, std::invoke_result_t>>, std::nullptr_t> = nullptr> auto comparator(const ToKey& to_key, const CompKey& comp_key = std::less<>()) { return [=](const T& x, const T& y) { return comp_key(to_key(x), to_key(y)); }; } template , std::nullptr_t> = nullptr> std::vector sorted_indices(int n, const Compare& compare) { std::vector p(n); return std::iota(p.begin(), p.end(), 0), std::sort(p.begin(), p.end(), compare), p; } template , std::nullptr_t> = nullptr> std::vector sorted_indices(int n, const ToKey& to_key) { return sorted_indices(n, comparator(to_key)); } template auto priority_queue_with_comparator(const Comparator& comparator) { return std::priority_queue, Comparator>{ comparator }; } template , std::nullptr_t> = nullptr> void sort_unique_erase(Iterable& a) { std::sort(a.begin(), a.end()), a.erase(std::unique(a.begin(), a.end()), a.end()); } template struct Dim : std::array { template Dim(const Ints& ...ns) : std::array::array{ static_cast(ns)... } {} }; template Dim(const Ints& ...) -> Dim; template auto ndvec(const Dim &ns, const T& value = {}) { if constexpr (I + 1 < D) { return std::vector(ns[I], ndvec(ns, value)); } else { return std::vector(ns[I], value); } } } namespace suisen { using int128 = __int128_t; using uint128 = __uint128_t; template using min_priority_queue = std::priority_queue, std::greater>; template using max_priority_queue = std::priority_queue, std::less>; } namespace suisen { const std::string Yes = "Yes", No = "No", YES = "YES", NO = "NO"; } #ifdef LOCAL # define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__) template void debug_impl(const char* s, const H& h, const Ts&... t) { suisen::io::cerr << "[\033[32mDEBUG\033[m] " << s << ": " << h, ((suisen::io::cerr << ", " << t), ..., (suisen::io::cerr << "\n")); } #else # define debug(...) void(0) #endif #define FOR(e, v) for (auto &&e : v) #define CFOR(e, v) for (const auto &e : v) #define REP(i, ...) CFOR(i, suisen::macro::rep_impl(__VA_ARGS__)) #define RREP(i, ...) CFOR(i, suisen::macro::rrep_impl(__VA_ARGS__)) #define REPINF(i, ...) CFOR(i, suisen::macro::repinf_impl(__VA_ARGS__)) #define LOOP(n) for ([[maybe_unused]] const auto& _ : suisen::macro::rep_impl(n)) #define ALL(iterable) std::begin(iterable), std::end(iterable) using namespace suisen; using namespace std; struct io_setup { io_setup(int precision = 20) { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(precision); } } io_setup_ {}; constexpr int iinf = std::numeric_limits::max() / 2; constexpr long long linf = std::numeric_limits::max() / 2; void solve() { int n, m; read(n, m); vector w_(n), v_(n); { long long sd, a, b, m; read(sd, a, b, m); vector f(2 * n); f[0] = sd; REP(i, 1, 2 * n) { f[i] = (a * f[i - 1] + b) % m; } REP(i, n) { w_[i] = f[i] % 3 + 1; v_[i] = w_[i] * f[n + i]; } } debug(w_, v_); array, 4> vs{}; REP(i, n) { vs[w_[i]].push_back(v_[i]); } vs[1].resize(3 * n, 0); vs[2].resize(n, 0); vs[3].resize(n, 0); REP(w, 1, 4) { sort(ALL(vs[w]), greater<>()); } array, 4> ss{}; REP(w, 1, 4) { ss[w].resize(vs[w].size() + 1); REP(i, vs[w].size()) ss[w][i + 1] = vs[w][i] + ss[w][i]; debug(ss[w]); } long long ans = -linf; REP(j, m + 1) { auto eval = [&](int i) { return ss[2][j] + ss[1][j + 3 * i] + ss[3][m - j - i]; }; int l = 0, r = m - j; while (r - l >= 3) { int ml = l + (r - l) / 3; int mr = r - (r - l) / 3; if (eval(ml) < eval(mr)) { l = ml; } else { r = mr; } } REP(i, l, r + 1) chmax(ans, eval(i)); } print(ans); } int main() { int test_case_num = 1; // read(test_case_num); LOOP(test_case_num) solve(); return 0; }