// https://github.com/miscalculation53/library/tree/wip/template/template_all.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_all_but_modint.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_types.hpp #include namespace { using namespace std; using ll = long long; using uint = unsigned int; using ull = unsigned long long; using pll = pair; #define vc vector using vl = vc; using i128 = __int128_t; using u128 = __uint128_t; #define cauto const auto // https://github.com/miscalculation53/library/tree/wip/template/template_rep.hpp #define overload4(_1,_2,_3,_4,name,...) name #define rep1(i,n) for (ll i = 0, nnnnn = ll(n); i < nnnnn; i++) #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi1(i,n) for (int i = 0, nnnnn = int(n); i < nnnnn; i++) #define repi(...) overload4(__VA_ARGS__, repi3, repi2, repi1)(__VA_ARGS__) #define fe(...) for (auto __VA_ARGS__) // https://github.com/miscalculation53/library/tree/wip/template/template_math.hpp // https://github.com/miscalculation53/library/tree/wip/utils/is_integral_ext.hpp template constexpr bool is_integral_ext = is_integral_v || is_same_v || is_same_v; template constexpr bool is_signed_ext = is_signed_v || is_same_v; template constexpr bool is_unsigned_ext = is_unsigned_v || is_same_v; // https://github.com/miscalculation53/library/tree/wip/utils/default_infty.hpp namespace default_infty_detail { template inline constexpr bool unsupported = false; } template && is_integral_ext>> inline constexpr T divfloor(U a, V b) { return T(a) / T(b) - (T(a) % T(b) && (T(a) ^ T(b)) < 0); } template && is_integral_ext>> inline constexpr T divceil(U a, V b) { return T(a) / T(b) + (T(a) % T(b) && (T(a) ^ T(b)) >= 0); } template && is_integral_ext>> inline constexpr T safemod(U a, V b) { return T(a) - T(b) * divfloor(a, b); } // https://github.com/miscalculation53/library/tree/wip/template/template_vector.hpp #define ALL(a) (a).begin(), (a).end() // https://github.com/miscalculation53/library/tree/wip/template/template_algo.hpp // https://github.com/miscalculation53/library/tree/wip/utils/resolved_infty.hpp // https://github.com/miscalculation53/library/tree/wip/utils/resolved_value.hpp template auto MAX(const V &v) { return *max_element(ALL(v)); } template struct has_e0 : false_type {}; template struct has_e0> : true_type {}; template inline constexpr bool has_e0_v = has_e0::value; namespace internal { } template vc cuml(const vc &v, int left_index = 0) { const int n = v.size(); vc res(n + 1); res[0] = M::e(); repi(i, n) res[i + 1] = M::op(res[i], v[i]); res.erase(res.begin(), res.begin() + left_index); return res; } constexpr array DRULgrid = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}; constexpr array DRULplane = {{{0, -1}, {1, 0}, {0, 1}, {-1, 0}}}; // https://github.com/miscalculation53/library/tree/wip/template/template_binsearch.hpp template struct is_random_access_iterator { static constexpr bool value = is_same_v< typename iterator_traits::iterator_category, random_access_iterator_tag >; }; template constexpr bool is_random_access_iterator_v = is_random_access_iterator::value; namespace internal { }; // https://github.com/miscalculation53/library/tree/wip/template/template_bit.hpp template inline constexpr ull MASK(T k) { return (1ULL << k) - 1ULL; } inline constexpr ll bit_width(ll x) { return std::bit_width((ull)x); } inline constexpr ll bit_floor(ll x) { return std::bit_floor((ull)x); } inline constexpr ll bit_ceil(ll x) { return std::bit_ceil((ull)x); } inline constexpr ll countr_zero(ll x) { assert(x != 0); return std::countr_zero((ull)x); } inline constexpr ll popcount(ll x) { return std::popcount((ull)x); } inline constexpr bool has_single_bit(ll x) { return std::has_single_bit((ull)x); } // https://github.com/miscalculation53/library/tree/wip/template/template_inout.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_dump.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_dump_map.hpp #define dump(...) #define local(...) #define oj(...) __VA_ARGS__ namespace fastio { template struct unsigned_integer { using type = make_unsigned_t; }; template <> struct unsigned_integer { using type = u128; }; template <> struct unsigned_integer { using type = u128; }; template using unsigned_integer_t = typename unsigned_integer::type; static constexpr uint32_t SIZ = 1 << 17; char ibuf[SIZ]; char obuf[SIZ]; char out[100]; uint32_t pil = 0, pir = 0, por = 0; struct Pre { char num[10000][4]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i][j] = n % 10 | '0'; n /= 10; } } } } constexpr pre; inline void load() { memcpy(ibuf, ibuf + pil, pir - pil); pir = pir - pil + fread(ibuf + pir - pil, 1, SIZ - pir + pil, stdin); pil = 0; if (pir < SIZ) ibuf[pir++] = '\n'; } inline void flush() { fwrite(obuf, 1, por, stdout); por = 0; } void rd1(string &x) { x.clear(); while (true) { if (pil == pir) load(); while (pil < pir && ibuf[pil] <= ' ') ++pil; if (pil < pir) break; } while (true) { uint32_t p = pil; while (pil < pir && ibuf[pil] > ' ') ++pil; x.append(ibuf + p, pil - p); if (pil < pir) { ++pil; return; } load(); } } template void rd1_integer(T &x) { using U = unsigned_integer_t; bool minus = false; U val = 0; if constexpr (check_buffer) if (pil + 100 > pir) load(); uint32_t p = pil; while (ibuf[p] < '-') ++p; if constexpr (is_signed::value || is_same_v) { if (ibuf[p] == '-') minus = true, ++p; } while ('0' <= ibuf[p]) val = val * 10 + (ibuf[p++] & 15); pil = p; if constexpr (is_signed::value || is_same_v) { if (minus) { const U min_abs = U(numeric_limits::max()) + 1; x = val == min_abs ? numeric_limits::lowest() : -T(val); } else x = T(val); } else x = T(val); } void rd1(ll &x) { rd1_integer(x); } template void rd1(pair &p) { return rd1(p.first), rd1(p.second); } template void rd1(vc &x) { for (auto &d: x) rd1(d); } template void read(T &...x) { if constexpr (sizeof...(T) <= SIZ / 100 && ((!is_same_v && (is_integral_v || is_same_v || is_same_v)) && ...)) { if (pil + 100 * sizeof...(T) > pir) load(); (rd1_integer(x), ...); } else (rd1(x), ...); } void wt1(const char c) { if (por == SIZ) flush(); obuf[por++] = c; } void wt1(string_view s) { while (!s.empty()) { if (por == SIZ) flush(); size_t n = min(s.size(), SIZ - por); memcpy(obuf + por, s.data(), n); por += n; s.remove_prefix(n); } } template void wt1_integer(T x) { if (por > SIZ - 100) flush(); using U = unsigned_integer_t; U ux; if constexpr (is_signed::value || is_same_v) { if (x < 0) obuf[por++] = '-', ux = U(0) - U(x); else ux = U(x); } else ux = x; int outi; for (outi = 96; ux >= 10000; outi -= 4) { memcpy(out + outi, pre.num[ux % 10000], 4); ux /= 10000; } if (ux >= 1000) { memcpy(obuf + por, pre.num[ux], 4); por += 4; } else if (ux >= 100) { memcpy(obuf + por, pre.num[ux] + 1, 3); por += 3; } else if (ux >= 10) { int q = (ux * 103) >> 10; obuf[por] = q | '0'; obuf[por + 1] = (ux - q * 10) | '0'; por += 2; } else obuf[por++] = ux | '0'; memcpy(obuf + por, out + outi + 4, 96 - outi); por += 96 - outi; } template , int> = 0> void wt1(T x) { wt1_integer(x); } template void wt1(const pair &val); template void wt1(const tuple &tpl); template void wt1(const array &val); template void wt1(const vector &val); template void write(T &&...x) { (wt1(std::forward(x)), ...); } template void print(T &&...x) { if constexpr (sizeof...(T)) { int i = 0; ((i++ ? wt1(' ') : void(), wt1(std::forward(x))), ...); } wt1('\n'); } } struct Dummy { Dummy() { atexit(fastio::flush); } } dummy; namespace internal { template void READnodump(Ts &...a) { fastio::read(a...); } template void READVECnodump(int n, vc &...v) { (v.resize(n), ...); READnodump(v...); } }; #define READ(...) internal::READnodump(__VA_ARGS__); dump(__VA_ARGS__) #define IN(T,...) T __VA_ARGS__; READ(__VA_ARGS__) #define LL(...) IN(ll, __VA_ARGS__) #define READVEC(...) internal::READVECnodump(__VA_ARGS__); dump(__VA_ARGS__) #define VEC(T,n,...) vc __VA_ARGS__; READVEC(n, __VA_ARGS__) #define PRINT fastio::print template pair &operator+=(pair &a, const P &b) { a.first += b.first; a.second += b.second; return a; } namespace internal { }; template void offset(vc &v, const Add &add) { for (auto &vi : v) vi += add; } template pair, vc> unzip(const vc> &vt) { const size_t n = vt.size(); pair, vc> tv; tv.first.resize(n), tv.second.resize(n); for (size_t i = 0; i < n; i++) tie(tv.first[i], tv.second[i]) = vt[i]; return tv; } namespace internal { }; #define UNZIP(vt,...) auto [__VA_ARGS__] = unzip(vt) // https://github.com/miscalculation53/library/tree/wip/template/template_random.hpp mt19937_64 mt; namespace internal { }; // https://github.com/miscalculation53/library/tree/wip/math/modint/template_modint.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/modint.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_static.hpp // https://github.com/miscalculation53/library/tree/wip/utils/larger_int.hpp namespace larger_int_detail { } template struct larger_int { private: static constexpr bool check(); static_assert(check()); public: using type = T; }; #define LARGER_INT(T,U) template <> struct larger_int { using type = U; }; LARGER_INT(signed char, short) LARGER_INT(short, int) LARGER_INT(int, long long) LARGER_INT(long, __int128_t) LARGER_INT(long long, __int128_t) LARGER_INT(unsigned char, unsigned short) LARGER_INT(unsigned short, unsigned int) LARGER_INT(unsigned int, unsigned long long) LARGER_INT(unsigned long, __uint128_t) LARGER_INT(unsigned long long, __uint128_t) #undef LARGER_INT template struct Rational; template struct larger_int> { using type = Rational::type>; }; template using larger_int_t = typename larger_int::type; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_isprime.hpp namespace internal { template constexpr ll powmod_constexpr(ll x, ll n, T m) { if (m == 1) return 0; using U = make_unsigned_t; using L = larger_int_t; U r = 1, y = safemod(x, m); while (n) { if (n & 1) r = L(r) * y % m; y = L(y) * y % m; n >>= 1; } return r; } template constexpr bool isprime = isprime_constexpr(n); }; namespace internal { template struct policy_static { using mod_type = decltype(M); using value_type = make_unsigned_t; using calc_type = larger_int_t; static constexpr bool is_prime = isprime_constexpr(M); static constexpr value_type init(value_type v) { return v; } static constexpr mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_barrett32.hpp namespace internal { struct barrett32 { uint m; ull im; explicit barrett32(uint m) : m(m), im((ull)(-1) / m + 1) {} }; template struct policy_barrett32 { using value_type = uint; using calc_type = ull; using mod_type = int; static constexpr bool is_prime = false; static inline barrett32 reducer{998244353}; static value_type init(value_type v) { return v; } static mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_montgomery64.hpp namespace internal { inline constexpr ull inv64(ull a) { ull x = a; while (a * x != 1) x *= 2 - a * x; return x; } struct montgomery64odd { ull m, im, sq; explicit montgomery64odd(ull m) : m(m), im(inv64(m)), sq(-u128(m) % m) {} ull reduce(u128 x) const { auto t = (x + u128(m) * (-im * ull(x))) >> 64; if (t >= m) t -= m; return (ull)t; } ull inv_reduce(i128 v) const { return reduce(u128(v % m + m) * sq); } }; struct montgomery64 { ull m, mx, imx, d, q; uint b; explicit montgomery64(ull m) : m(m) { b = countr_zero(m), mx = m >> b; imx = inv64(mx); d = powmod_constexpr((mx + 1) / 2, b, mx); u128 sq = -u128(mx) % mx; q = (1 + (((sq - 1) * d) << b)) % m; } ull umod() const { return m; } ull reduce(u128 x) const { if (b == 0) { auto t = (x + u128(mx) * (-imx * ull(x))) >> 64; if (t >= m) t -= m; return (ull)t; } ull p = x & MASK(b); x = (x >> b) + p * d; ull y = p << (64 - b); auto t = (x + u128(mx) * (imx * (y - ull(x)))) >> (64 - b); if (t >= m) { t -= m; if (t >= m) t -= m; } return (ull)t; } ull inv_reduce(i128 v) const { return reduce(u128(v % m + m) * q); } }; template struct policy_montgomery64_odd { using value_type = ull; using calc_type = u128; using mod_type = ll; static constexpr bool is_prime = false; static inline montgomery64odd reducer{(1LL << 61) - 1}; static value_type init(value_type v) { return reducer.inv_reduce(v); } static mod_type val(value_type v); }; template struct policy_montgomery64 { using value_type = ull; using calc_type = u128; using mod_type = ll; static constexpr bool is_prime = false; static inline montgomery64 reducer{(1LL << 61) - 1}; static value_type init(value_type v) { return reducer.inv_reduce(v); } static mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/extgcd.hpp namespace internal { template struct modint_impl { using V = typename Policy::value_type; using M = typename Policy::mod_type; using mint = modint_impl; private: V _v; public: modint_impl(); template >> modint_impl(T v); M val() const; friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; } friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; } friend void rd1(mint &x) { long long a; fastio::rd1(a); x = a; } friend void wt1(const mint &x) { fastio::wt1(x.val()); } }; }; template using static_modint32 = internal::modint_impl>; template using dynamic_modint32 = internal::modint_impl>; template using static_modint64 = internal::modint_impl>; template using dynamic_modint64_odd = internal::modint_impl>; template using dynamic_modint64 = internal::modint_impl>; using modint998244353 = static_modint32<998244353>; template struct is_modint : std::false_type { }; template struct is_modint> : std::true_type { }; template inline constexpr bool is_modint_v = is_modint::value; template struct is_static_modint : false_type {}; template struct is_static_modint> : true_type {}; template struct is_static_modint> : true_type {}; template inline constexpr bool is_static_modint_v = is_static_modint::value; template struct is_dynamic_modint : false_type {}; template struct is_dynamic_modint> : true_type {}; template struct is_dynamic_modint> : true_type {}; template struct is_dynamic_modint> : true_type {}; template inline constexpr bool is_dynamic_modint_v = is_dynamic_modint::value; // https://github.com/miscalculation53/library/tree/wip/math/modint/power_table.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/binomial.hpp template struct Binomial { private: inline static decltype(T::mod()) mod; public: inline static vc fac_, finv_, inv_; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/stom.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/to_rational.hpp // https://github.com/miscalculation53/library/tree/wip/math/svp2d.hpp namespace cpp_dump { template struct rat_value { T p, q; friend ostream &operator<<(ostream &os, const rat_value &x) { os << x.p; if (x.q != 1) os << '/' << x.q; return os; } }; template inline constexpr bool rat_is_map = false; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; } using mint = modint998244353; void init() { oj(mt.seed(random_device()())); } // https://github.com/miscalculation53/library/tree/wip/ds/cumulative_sum/imos.hpp // https://github.com/miscalculation53/library/tree/wip/algebra/algebra_basic_ops.hpp // https://github.com/miscalculation53/library/tree/wip/algebra/algebra_base.hpp template struct has_e1 : false_type {}; template struct has_e1> : true_type {}; template inline constexpr bool has_e1_v = has_e1::value; template struct GroupAddSub { using S = T; static constexpr S op(S a, S b) { return a + b; } static constexpr S e() { if constexpr (has_e0_v) return S::e0(); else return S{}; } static constexpr S inv(S a) { return -a; } }; template > struct Imos { using S = typename G::S; private: vc d; public: Imos(int n) : d(n, G::e()) {} void add(int l, int r, const S &v) { const int n = d.size(); assert(0 <= l && l <= r && r <= n); if (l == r) return; d[l] = G::op(d[l], v); if (r != n) d[r] = G::op(d[r], G::inv(v)); } vc content() { return cuml(d, 1); } }; vl f(ll N, vl A) { Imos imos0(2 * N), imos1(2 * N); fe(a : A) { ll mid = divceil(N, 2); imos0.add(a, a + mid, -a); imos1.add(a, a + mid, 1); imos0.add(a + mid, a + N, a + N); imos1.add(a + mid, a + N, -1); local( auto res0 = imos0.content(), res1 = imos1.content(); vl res(N); rep(i, 2 * N) res[i % N] += res0[i] + i * res1[i]; dump(res | cp::index()); ); } auto res0 = imos0.content(), res1 = imos1.content(); vl res(N); rep(i, 2 * N) res[i % N] += res0[i] + i * res1[i]; return res; } void main2() { LL(N, H, W); VEC(pll, N, IJ); offset(IJ, pll{-1, -1}); UNZIP(IJ, I, J); vl A = f(H, I), B = f(W, J); dump(A | cp::index(), B | cp::index()); PRINT(MAX(A) + MAX(B)); } void test() { } // https://github.com/miscalculation53/library/tree/wip/template/template_main.hpp template struct Main { Main() { cauto CERR = [](string val, string color) { string s = "\033[" + color + "m" + val + "\033[m"; }; CERR("\n[FAST_IO]\n\n", "32"); cout << fixed << setprecision(20); init(); CERR("\n[SINGLE_TESTCASE]\n\n", "36"); main2(); } }; Main main_dummy; } int main() {}