#include #include using namespace std; struct UF{ vector par,sz; vector> mergeTree; UF(int n, bool useMergeTree = false){ sz.resize(n); par.resize(n); for(int i=0;isz[y]) swap(x,y); sz[y] += sz[x]; par[x] = y; } bool same(int x,int y){return find(x)==find(y);} void merge(int child,int parent){ //parentが親,merge過程を表す木などで使用 child = find(child); parent = find(parent); if(child==parent) return; mergeTree[parent].push_back(child); sz[parent] += sz[child]; par[child] = parent; } }; #include #include #include typedef long long ll; using namespace std; vector H[5010],W[5010]; ll dp_mn[5010],dp_mx[5010],ndp_mn[5010],ndp_mx[5010],inf = 1000000000; int a[200010],b[200010]; int main(){ int i,j,h,w,n; cin >> h >> w >> n; UF ufh(h),ufw(w); for(i=0;i> a[i] >> b[i]; a[i]--; b[i]--; H[a[i]].push_back(b[i]); W[b[i]].push_back(a[i]); } for(i=0;i> s; for(i=0;i=h_c){ ndp_mx[i] = max(ndp_mx[i],dp_mx[i - h_c] + w_c); ndp_mn[i] = min(ndp_mn[i],dp_mn[i - h_c] + w_c); } ndp_mx[i] = max(ndp_mx[i],dp_mx[i]); ndp_mn[i] = min(ndp_mn[i],dp_mn[i]); } for(i=0;i<=h;i++){ dp_mx[i] = ndp_mx[i]; ndp_mx[i] = -inf; dp_mn[i] = ndp_mn[i]; ndp_mn[i] = inf; } } ll ans = 0; for(i=0;i<=h;i++){ // cout << i << " " << dp_mn[i] << " " << dp_mx[i] << "\n"; if(dp_mn[i]<=w) ans = max(ans,i*w + dp_mn[i]*h - dp_mn[i]*i*2); if(dp_mx[i]>=0) ans = max(ans,i*w + dp_mx[i]*h - dp_mx[i]*i*2); } cout << ans << "\n"; }