// Partial aimed ONLY at S5 (h non-decreasing AND w non-increasing).
// Under that guarantee a linear segment [j..i] has maxH = h_i and maxW = w_j, so
//   cost(j,i) = h_i * w_j,
// and the linear DP  dp[i] = max_{j<i} dp[j] + h_i * w_j  is a single max-CHT
// (lines slope=w_j, intercept=dp[j], queried at x=h_i), O(N log N).
// The cycle: either the seam is cut (solve linear on [0..n-1]), or the wrap arc is
// the two global extremes {n-1, 0} with area h_{n-1}*w_0 plus the linear best of
// [1..n-2]. Wrong on non-monotone inputs -> scores S5 only.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Line { mutable ll k,m,p; bool operator<(const Line&o)const{return k<o.k;} bool operator<(ll x)const{return p<x;} };
struct LineContainer : multiset<Line,less<>> {
    static const ll inf = LLONG_MAX;
    ll fdiv(ll a,ll b){ return a/b - ((a^b)<0 && a%b); }
    bool isect(iterator x,iterator y){
        if(y==end()) return x->p=inf,0;
        if(x->k==y->k) x->p = x->m>y->m?inf:-inf;
        else x->p=fdiv(y->m-x->m, x->k-y->k);
        return x->p>=y->p;
    }
    void add(ll k,ll m){
        auto z=insert({k,m,0}),y=z++,x=y;
        while(isect(y,z)) z=erase(z);
        if(x!=begin() && isect(--x,y)) isect(x,y=erase(y));
        while((y=x)!=begin() && (--x)->p >= y->p) isect(x,erase(y));
    }
    ll query(ll x){ auto l=*lower_bound(x); return l.k*x + l.m; }
};

static vector<ll> H, W;
// best partition sum of indices [lo, hi)  (monotone assumption)
static ll linsolve(int lo,int hi){
    int len=hi-lo;
    if(len<=0) return 0;
    vector<ll> dp(len+1,0);
    LineContainer cht;
    for(int i=1;i<=len;i++){
        cht.add(W[lo+i-1], dp[i-1]);     // line for j=i-1
        dp[i]=cht.query(H[lo+i-1]);      // max_{j<i} dp[j] + H[lo+i-1]*W[lo+j]
    }
    return dp[len];
}
long long solve(std::vector<int> H_in, std::vector<int> W_in){
    int n = (int)H_in.size();
    H.assign(H_in.begin(), H_in.end());
    W.assign(W_in.begin(), W_in.end());
    ll ans = linsolve(0,n);                                  // seam cut
    if(n>=2) ans = max(ans, H[n-1]*W[0] + linsolve(1,n-1));  // seam uncut: wrap {n-1,0}
    return ans;
}
