// #include // Temp fix for gcc13 global pragma // #pragma GCC target("avx2,bmi2,popcnt,lzcnt") // #pragma GCC optimize("O3,unroll-loops") #include // #include using namespace std; using namespace numbers; #ifdef LOCAL #include "Debug.h" #else #define debug_endl() 42 #define debug(...) 42 #define debug2(...) 42 #define debug_bin(...) 42 #endif // Returns the largest integer k with x >= k * y template U floor_div(T x, U y){ assert(y > 0); return x / y - (x % y < 0); } // Returns the smallest integer k with x <= k * y template U ceil_div(T x, U y){ assert(y > 0); return x / y + (x % y > 0); } template T &ctmin(T &x){ return x; } template T &ctmin(T &x, const Head &h, const Tail &... t){ return ctmin(x = min(x, h), t...); } template T &ctmax(T &x){ return x; } template T &ctmax(T &x, const Head &h, const Tail &... t){ return ctmax(x = max(x, h), t...); } // std::chunk_by cuz AtCoder is stuck on 3 years old gcc vector> chunk_by(auto data, auto eq){ vector> chunks; for(auto l = data.begin(); l != data.end(); ){ auto r = next(l); vector chunk{*l}; while(r != data.end() && eq(*prev(r), *r)){ chunk.push_back(*r); r = next(r); } chunks.push_back(chunk); l = r; } return chunks; } // Keeps track of piecewise linear function over real numbers x with left_boundary <= x < right_boundary // Each connected component must be left-closed and right-open template struct piecewise_linear_function_container{ #ifdef LOCAL #define ASSERT(x) assert(x) #else #define ASSERT(x) 42 #endif Key_t left_boundary, right_boundary; Value_t initial_value, initial_slope; map first_derivative; map second_derivative; void _update_1(Key_t x, Value_t value_dif){ ASSERT(left_boundary <= x && x < right_boundary); if(value_dif == Value_t{0}) return; if(x == left_boundary) initial_value += value_dif; else if((first_derivative[x] += value_dif) == 0) first_derivative.erase(x); } void _update_2(Key_t x, Value_t slope_dif){ ASSERT(left_boundary <= x && x < right_boundary); if(slope_dif == Value_t{0}) return; if(x == left_boundary) initial_slope += slope_dif; else if((second_derivative[x] += slope_dif) == 0) second_derivative.erase(x); } piecewise_linear_function_container( Key_t left_boundary = numeric_limits::min(), Key_t right_boundary = numeric_limits::max(), Value_t initial_value = 0, Value_t initial_slope = 0 ): left_boundary(left_boundary), right_boundary(right_boundary), initial_value(initial_value), initial_slope(initial_slope){ ASSERT(left_boundary < right_boundary); } void clear( Key_t left_boundary = numeric_limits::min(), Key_t right_boundary = numeric_limits::max(), Value_t initial_value = 0, Value_t initial_slope = 0 ){ ASSERT(left_boundary < right_boundary); this->left_boundary = left_boundary; this->right_boundary = right_boundary; this->initial_value = initial_value; this->initial_slope = initial_slope; first_derivative.clear(); second_derivative.clear(); } // Add value + slope * (x - l) at x for each l <= x < r void add(Key_t l, Key_t r, Value_t value, Value_t slope){ ASSERT(l <= r); r = clamp(r, left_boundary, right_boundary); if(l < left_boundary){ value += slope * (left_boundary - l); l = left_boundary; } l = min(l, right_boundary); if(l == r) return; _update_1(l, value); _update_2(l, slope); if(r < right_boundary){ _update_1(r, -value - slope * (r - l)); _update_2(r, -slope); } } // Add value_reversed + slope_reversed * (r - x) at x for each l <= x < r void add_reversed(Key_t l, Key_t r, Value_t value_reversed, Value_t slope_reversed){ add(l, r, value_reversed + slope_reversed * (r - l), -slope_reversed); } // Add connected piecewise line, left-closed and right-open, connecting the given points in order void add_piecewise_line(vector> piecewise_line){ for(auto i = 0; i + 1 < (int)piecewise_line.size(); ++ i) ASSERT(piecewise_line[i].first < piecewise_line[i + 1].first); if((int)piecewise_line.size() < 2 || piecewise_line.back().first <= left_boundary || right_boundary <= piecewise_line.front().first) return; int head = 0; while(head + 1 < (int)piecewise_line.size() && piecewise_line[head + 1].first <= left_boundary) ++ head; piecewise_line.erase(piecewise_line.begin(), piecewise_line.begin() + head); if(piecewise_line[0].first < left_boundary){ Value_t slope = (piecewise_line[1].second - piecewise_line[0].second) / (piecewise_line[1].first - piecewise_line[0].first); piecewise_line[0] = {left_boundary, piecewise_line[0].second + slope * (left_boundary - piecewise_line[0].first)}; } while((int)piecewise_line.size() >= 2 && piecewise_line.end()[-2].first >= right_boundary) piecewise_line.pop_back(); if(piecewise_line.end()[-1].first > right_boundary){ Value_t slope = (piecewise_line.end()[-2].second - piecewise_line.end()[-1].second) / (piecewise_line.end()[-2].first - piecewise_line.end()[-1].first); piecewise_line.end()[-1] = {right_boundary, piecewise_line.end()[-1].second + slope * (right_boundary - piecewise_line.end()[-1].first)}; } _update_1(piecewise_line.front().first, piecewise_line.front().second); Value_t slope = 0; for(auto i = 0; i + 1 < (int)piecewise_line.size(); ++ i){ Value_t next_slope = (piecewise_line[i + 1].second - piecewise_line[i].second) / (piecewise_line[i + 1].first - piecewise_line[i].first); _update_2(piecewise_line[i].first, next_slope - slope); slope = next_slope; } if(piecewise_line.back().first < right_boundary){ _update_1(piecewise_line.back().first, -piecewise_line.back().second); _update_2(piecewise_line.back().first, -slope); } } void add_piecewise_line(int n, auto f){ ASSERT(n >= 0); vector> piecewise_line(n); for(auto i = 0; i < n; ++ i) piecewise_line[i] = f(i); add_piecewise_line(piecewise_line); } void set_left_boundary(Key_t new_left_boundary, auto process){ ASSERT(left_boundary <= new_left_boundary && new_left_boundary < right_boundary); if(new_left_boundary == left_boundary) return; Key_t pos = left_boundary; Value_t value = initial_value; Value_t slope = initial_slope; auto it1 = first_derivative.begin(); auto it2 = second_derivative.begin(); for(; it2 != second_derivative.end() && it2->first <= new_left_boundary; it2 = second_derivative.erase(it2)){ for(; it1 != first_derivative.end() && it1->first <= it2->first; it1 = first_derivative.erase(it1)){ process(pos, it1->first, value, slope); value += it1->second + slope * (it1->first - pos); pos = it1->first; } if(pos < it2->first) process(pos, it2->first, value, slope); value += slope * (it2->first - pos); slope += it2->second; pos = it2->first; } for(; it1 != first_derivative.end() && it1->first <= new_left_boundary; it1 = first_derivative.erase(it1)){ process(pos, it1->first, value, slope); value += it1->second + slope * (it1->first - pos); pos = it1->first; } if(pos < new_left_boundary){ process(pos, new_left_boundary, value, slope); value += slope * (new_left_boundary - pos); pos = new_left_boundary; } left_boundary = new_left_boundary; initial_value = value; initial_slope = slope; } void set_left_boundary(Key_t new_left_boundary){ set_left_boundary(new_left_boundary, [&](Key_t, Key_t, Value_t, Value_t){ }); } // Return {left, right, value, slope} of the leftmost line segment tuple eval_left_line_segment() const{ Key_t right = right_boundary; if(!first_derivative.empty() && (second_derivative.empty() || first_derivative.begin()->first <= second_derivative.begin()->first)) right = first_derivative.begin()->first; else if(!second_derivative.empty()) right = second_derivative.begin()->first; return {left_boundary, right, initial_value, initial_slope}; } // Split [l, r) into maximal intervals [p_0=l, p_1), [p_1, p_2), ..., [p_{k-2}, p_{k-1}=r) // such that p_i < p_{i+1} and [p_i, p_{i+1}) is a line segment // Call process_while(p_i, p_{i+1}, value at p_i, slope) for each such intervals in increasing order of i void iterate_all_line_segments(Key_t l, Key_t r, auto process_while) const{ ASSERT(left_boundary <= l && l <= r && r <= right_boundary); if(l == r) return; Key_t pos = left_boundary; Value_t value = initial_value; Value_t slope = initial_slope; auto it1 = first_derivative.begin(); auto it2 = second_derivative.begin(); for(; it2 != second_derivative.end() && it2->first <= l; ++ it2){ for(; it1 != first_derivative.end() && it1->first <= it2->first; ++ it1) value += it1->second; value += slope * (it2->first - pos); slope += it2->second; pos = it2->first; } for(; it1 != first_derivative.end() && it1->first <= l; ++ it1) value += it1->second; value += slope * (l - pos); pos = l; for(; it2 != second_derivative.end() && it2->first < r; ++ it2){ for(; it1 != first_derivative.end() && it1->first <= it2->first; ++ it1){ if(!process_while(pos, it1->first, value, slope)) return; value += it1->second + slope * (it1->first - pos); pos = it1->first; } if(pos < it2->first) if(!process_while(pos, it2->first, value, slope)) return; value += slope * (it2->first - pos); slope += it2->second; pos = it2->first; } for(; it1 != first_derivative.end() && it1->first < r; ++ it1){ if(!process_while(pos, it1->first, value, slope)) return; value += it1->second + slope * (it1->first - pos); pos = it1->first; } process_while(pos, r, value, slope); } friend ostream &operator<<(ostream &out, const piecewise_linear_function_container &plfc){ out << "\n"; bool first = true; bool from_found = false; Key_t from = plfc.left_boundary; Key_t to = plfc.left_boundary; plfc.iterate_all_line_segments(plfc.left_boundary, plfc.right_boundary, [&](Key_t l, Key_t r, Value_t value, Value_t slope){ if(first) out << "(" << l << ", " << value << ")", first = false; out << "<" << slope << ">(" << r << ", " << value + slope * (r - l) << ")"; if(value || slope){ if(!from_found){ from_found = true; from = l; } to = r; } return true; }); out << "\n"; vector a(to - from + 1); plfc.iterate_all_line_segments(plfc.left_boundary, plfc.right_boundary, [&](Key_t l, Key_t r, Value_t value, Value_t slope){ if(from <= l && r <= to) for(auto i = l; i <= r; ++ i) a[i - from] = value + slope * (i - l); return true; }); out << "[" << from << " ~ " << to << "]: {"; for(auto i = 0; i <= to - from; ++ i){ out << a[i]; if(i + 1 <= to - from) out << ", "; } return out << "}"; } #undef ASSERT }; int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n; long long nr, nc; cin >> n >> nr >> nc; vector rs(n), cs(n); for(auto i = 0; i < n; ++ i){ cin >> rs[i] >> cs[i], -- rs[i], -- cs[i]; } long long res = 0; for(auto _ = 0; _ < 2; ++ _){ piecewise_linear_function_container container; for(auto x: rs){ if(nr & 1){ container.add_piecewise_line(vector>{ {x - nr / 2 - nr, nr / 2}, {x - nr, 0}, {x + nr / 2 - nr, nr / 2}, {x - nr / 2, nr / 2}, {x, 0}, {x + nr / 2, nr / 2}, {x - nr / 2 + nr, nr / 2}, {x + nr, 0}, {x + nr / 2 + nr, nr / 2}, }); } else{ container.add_piecewise_line(vector>{ {x - nr / 2 * 3, nr / 2}, {x - nr, 0}, {x - nr / 2, nr / 2}, {x, 0}, {x + nr / 2, nr / 2}, {x + nr, 0}, {x + nr / 2 * 3, nr / 2}, }); } } long long cur = 0; container.iterate_all_line_segments(0, nr - 1, [&](long long l, long long r, long long x, long long slope){ ctmax(cur, max(x, x + slope * (r - l))); return true; }); res += cur; swap(nr, nc); swap(rs, cs); } cout << res << "\n"; return 0; } /* */