#include using namespace std; long long mod = 998244353; //入力が必ずmod未満の時に使う. struct mint{ long long v = 0; mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;} long long val(){return v;} void modu(){v %= mod;} mint repeat2mint(const long long a,long long b){ mint ret = 1,p = a; while(b){ if(b&1) ret *= p; p *= p; b >>= 1; } return ret; }; mint operator+(const mint b){return mint(v)+=b;} mint operator-(const mint b){return mint(v)-=b;} mint operator*(const mint b){return mint(v)*=b;} mint operator/(const mint b){return mint(v)/=b;} mint operator+=(const mint b){ v += b.v; if(v >= mod) v -= mod; return *this; } mint operator-=(const mint b){ v -= b.v; if(v < 0) v += mod; return *this; } mint operator*=(const mint b){v = v*b.v%mod; return *this;} mint operator/=(mint b){ if(b == 0) assert(false); int left = mod-2; while(left){if(left&1) *this *= b; b *= b; left >>= 1;} return *this; } mint operator++(int){*this += 1; return *this;} mint operator--(int){*this -= 1; return *this;} bool operator==(const mint b){return v == b.v;} bool operator!=(const mint b){return v != b.v;} bool operator>(const mint b){return v > b.v;} bool operator>=(const mint b){return v >= b.v;} bool operator<(const mint b){return v < b.v;} bool operator<=(const mint b){return v <= b.v;} mint pow(const long long x){return repeat2mint(v,x);} mint inv(){return mint(1)/v;} }; namespace to_fold{ //纏めて折り畳むためのやつ 苦労したが結局ほぼACLの写経. __int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;} pair invgcd(long long a,long long b){ //return {gcd(a,b),x} (xa≡g(mod b)) a = safemod(a,b); if(a == 0) return {b,0}; long long x = 0,y = 1,memob = b; while(a){ long long q = b/a; b -= a*q; swap(x,y); y -= q*x; swap(a,b); } if(x < 0) x += memob/b; return {b,x}; } long long Garner(vector &A,vector &M){ __int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須. for(int i=1; i root,iroot,rate2,irate2,rate3,irate3; fftinfo(mint g){ int rank2 = countzero(mod-1); root.resize(rank2+1),iroot = root; rate2.resize(max(0,rank2-2+1)); irate2 = rate2; rate3.resize(max(0,rank2-3+1)); irate3 = rate3; root[rank2] = g.pow((mod-1)>>rank2); iroot[rank2] = root[rank2].inv(); for(int i=rank2-1; i>=0; i--){ root[i] = root[i+1]*root[i+1]; iroot[i] = iroot[i+1]*iroot[i+1]; } mint mul = 1,imul = 1; for(int i=0; i<=rank2-2; i++){ rate2[i] = root[i+2]*mul; irate2[i] = iroot[i+2]*imul; mul *= iroot[i+2],imul *= root[i+2]; } mul = 1,imul = 1; for(int i=0; i<=rank2-3; i++){ rate3[i] = root[i+3]*mul; irate3[i] = iroot[i+3]*imul; mul *= iroot[i+3],imul *= root[i+3]; } } }; mint findroot(){ if(mod == 998244353) return mint(3); else if(mod == 754974721) return mint(11); else if(mod == 167772161) return mint(3); else if(mod == 469762049) return mint(3); long long p = mod-1; vector P; for(long long i=2; i*i<=p; i++){ if(p%i) continue; while(p%i == 0) p /= i; P.push_back(i); } if(p != 1) P.push_back(p); p = mod-1; random_device rnd; mt19937 mt(rnd()); while(true){ mint ret = mt()%mod; if(ret == 1 || ret == 0) continue; if(ret.pow(p) != 1) continue; bool ok = true; for(auto check : P) if(ret.pow(p/check) == 1){ok = false; break;} if(ok) return ret; } //O(√P)らしいです. } void NTT(vector &A,fftinfo &info){ int N = A.size(),ln = countzero(N); int dep = 0; while(dep < ln){ if(ln-dep == 1){ int p = 1<<(ln-dep-1); mint rot = 1; for(int o=0; o<(1< &A,fftinfo &info){ int N = A.size(),ln = countzero(N); int dep = ln; while(dep){ if(dep == 1){ int p = 1<<(ln-dep); mint irot = 1; for(int o=0; o<(1<<(dep-1)); o++){ int offset = o<<(ln-dep+1); for(int i=0; i convolutionnaive(vector &A,vector &B){ vector ret(A.size()+B.size()-1); for(int i=0; i convolution(vector &A,vector &B){ int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1; if(siza == 0 || sizb == 0) return {}; while(N <= sizc) N <<= 1; vector ca = A,cb = B; ca.resize(N),cb.resize(N); if(min(siza,sizb) <= 40) return convolutionnaive(A,B); assert((mod-1)%N == 0); mint root = findroot(); fftinfo info(root); NTT(ca,info); NTT(cb,info); for(int i=0; i convolution_ll(vector &A,vector &B){ int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1; if(siza == 0 || sizb == 0) return {}; unsigned long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049; unsigned long long m1m2 = mod1*mod2,m2m3 = mod2*mod3,m3m1 = mod3*mod1,m1m2m3 = mod1*mod2*mod3; unsigned long long i1 = invgcd(m2m3,mod1).second,i2 = invgcd(m3m1,mod2).second,i3 = invgcd(m1m2,mod3).second; assert(sizc <= (1<<24)); mod = mod1; vector a(siza),b(sizb); for(int i=0; i C1 = convolution(a,b); mod = mod2; for(int i=0; i C2 = convolution(a,b); mod = mod3; for(int i=0; i C3 = convolution(a,b); vector ret(sizc); vector offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3}; for(int i=0; i convolution_llmod(vector &A,vector &B,long long memomod){ int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1; if(siza == 0 || sizb == 0) return {}; long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049; assert(sizc <= (1<<24)); mod = mod1; vector a(siza),b(sizb); for(int i=0; i C1 = convolution(a,b); mod = mod2; for(int i=0; i C2 = convolution(a,b); mod = mod3; for(int i=0; i C3 = convolution(a,b); mod = memomod; vector ret(sizc); for(int i=0; i A = {C1.at(i).v,C2.at(i).v,C3.at(i).v}; vector M = {mod1,mod2,mod3}; ret.at(i) = Garner(A,M); } return ret; } } using namespace to_fold; class UnionFind{ public: vector par,siz; void make(int N){ par.resize(N,-1); siz.resize(N,1); } int root(int x){ if(par.at(x) == -1) return x; else return par.at(x) = root(par.at(x)); } void unite(int u, int v){ u = root(u),v = root(v); if(u == v) return; if(siz.at(u) < siz.at(v)) swap(u,v); par.at(v) = u; siz.at(u) += siz.at(v); } bool issame(int u, int v){ if(root(u) == root(v)) return true; else return false; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int H,W,N; cin >> H >> W >> N; UnionFind uf; uf.make(H+W); while(N--){ int a,b; cin >> a >> b; a--; b--; b += H; uf.unite(a,b); } int X = 0,Y = 0; vector> need(H+W); for(int i=0; i>> Q((H+1)*(W+1)+1); for(auto &[x,y] : need) if(x || y){ if(x == 1 && y == 0) X++; else if(x == 0 && y == 1) Y++; else{ left++; vector now; while(now.size() < x*(W+1)+y+1) now.push_back(0); now.at(0) = 1,now.back() = 1; Q.at(now.size()).push_back(now); } } int pos = 0,pos2 = 0; while(left > 1){ while(Q.at(pos).size() <= pos2) pos++,pos2 = 0; auto &A = Q.at(pos).at(pos2++); while(Q.at(pos).size() <= pos2) pos++,pos2 = 0; auto &B = Q.at(pos).at(pos2++); auto C = convolution(A,B); for(auto &c : C) if(c != 0) c = 1; A.clear(),B.clear(); Q.at(C.size()).push_back(C); left--; } while(Q.back().size() == 0) Q.pop_back(); auto &A = Q.back().back(); while(A.size() < (H+1)*(W+1)) A.push_back(0); int answer = 0; for(int i=0; i<=H; i++) for(int k=0; k<=W; k++){ int pos = i*(W+1)+k; if(A.at(pos) == 0) continue; answer = max(answer,i*W+k*H-2*i*k); int nowy = Y; for(int x=0; x<=X&&i+x<=H; x++){ if(nowy == -1) break; for(int y=0; y<=Y&&k+y<=W; y++){ if((x || y) && A.at(pos+y) == 1){nowy = y-1; break;} answer = max(answer,(i+x)*W+(k+y)*H-2*(i+x)*(k+y)); } pos += W+1; } } cout << answer << endl; }