// Partial: O(N^2) interval DP with the same cyclic reduction as the model solution
// (rotate the global-max-height element to the front; solve linear; reverse+rotate; solve).
// Intended for S1-S3 (N<=4000); TLEs for N up to 3e5 (S4/S5/S6).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static ll linsolve(const vector<ll>& h, const vector<ll>& w){
    int n=h.size();
    vector<ll> dp(n+1, 0);
    for(int i=1;i<=n;i++){
        ll mh=0,mw=0,best=LLONG_MIN;
        for(int j=i-1;j>=0;j--){
            mh=max(mh,h[j]); mw=max(mw,w[j]);
            best=max(best, dp[j]+mh*mw);
        }
        dp[i]=best;
    }
    return dp[n];
}
long long solve(std::vector<int> H_in, std::vector<int> W_in){
    int n = (int)H_in.size();
    vector<ll> h(H_in.begin(), H_in.end()), w(W_in.begin(), W_in.end());
    int start=max_element(h.begin(),h.end())-h.begin();
    rotate(h.begin(),h.begin()+start,h.end());
    rotate(w.begin(),w.begin()+start,w.end());
    ll ans=linsolve(h,w);
    reverse(h.begin(),h.end()); reverse(w.begin(),w.end());
    rotate(h.begin(),h.begin()+(n-1),h.end());
    rotate(w.begin(),w.begin()+(n-1),w.end());
    ans=max(ans, linsolve(h,w));
    return ans;
}
