#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <numeric>

struct Rational
{
	Rational(int64_t n, int64_t d) : num(n), denom(d) 
    {
        if (denom < 0)
        {
            num *= -1;
            denom *= -1;
        }
		int64_t g = std::gcd(num, denom);
        num /= g;
        denom /= g;
    }

    bool operator<(const Rational& other) const
    {
        return __int128(num) * __int128(other.denom) < __int128(other.num) * __int128(denom);
	}

    bool operator<=(const Rational& other) const
    {
        return __int128(num) * __int128(other.denom) <= __int128(other.num) * __int128(denom);
    }

    int64_t num;
    int64_t denom;
};

int64_t solve(const std::vector<int64_t>& h, const std::vector<int64_t>& w)
{
    struct Item
    {
        int64_t h;
        int64_t w;
        int64_t score;
        Rational hStart;
        Rational wStart;
    };

    auto hComp = [](const Item& a, const Item& b)
        {
            if (a.h < b.h)
                return true;
            else if (a.h > b.h)
                return false;
            return a.score < b.score;
        };
    auto wComp = [](const Item& a, const Item& b)
        {
            if (a.w < b.w)
                return true;
            else if (a.w > b.w)
                return false;
            return a.score < b.score;
        };
    auto hStartComp = [](const Item& a, const Item& b) { return a.hStart < b.hStart; };
    auto wStartComp = [](const Item& a, const Item& b) { return a.wStart < b.wStart; };
    std::set<Item, decltype(hComp)> hSet(hComp);
    std::set<Item, decltype(wComp)> wSet(wComp);
    std::set<Item, decltype(hStartComp)> hStartSet(hStartComp);
    std::set<Item, decltype(wStartComp)> wStartSet(wStartComp);

    int n = h.size();
    std::vector<int64_t> dp(n + 1);
    for (int i = 0; i < n; i++)
    {
        Rational Rw(w[i], 1);
        Rational Rh(h[i], 1);
        
        int64_t option1 = dp[i] + h[i] * w[i];

		Item newItem{ h[i], w[i], dp[i], Rh, Rw};
        
		Item searchItem{ 0, 0, 0, Rw, Rh };
        auto it = hStartSet.upper_bound(searchItem);
        int64_t option2 = 0;
        if (it != hStartSet.begin())
        {
            --it;
			option2 = it->score + it->h * w[i];
        }

        auto it2 = wStartSet.upper_bound(searchItem);
        int64_t option3 = 0;
        if (it2 != wStartSet.begin())
        {
            --it2;
            option3 = it2->score + it2->w * h[i];
        }

        dp[i + 1] = std::max(option1, std::max(option2, option3));
		
        std::vector<Item> toRemove;
        Rational newRh(0, 1);
        auto hIt = hSet.upper_bound(newItem);

        auto hprev = hIt;
        while(hprev != hSet.begin())
        {
            --hprev;
            if (hprev->h == newItem.h)
            {
                toRemove.push_back(*hprev);
                continue;
            }

            Rational iSect = Rational(hprev->score - newItem.score, newItem.h - hprev->h);
            if (iSect <= hprev->hStart)
            {
                toRemove.push_back(*hprev);
                continue;
            }
            else
            {
                newRh = iSect;
                break;
			}
        }

        Rational nextRh(1, 0);
        while (hIt != hSet.end())
        {
            if (hIt->h == newItem.h)
            {
                nextRh = Rational(0, 1);
                break;
            }
            Rational iSect = Rational(hIt->score - newItem.score, newItem.h - hIt->h);
            nextRh = iSect;
            auto nhIt = std::next(hIt);
            if (nhIt != hSet.end() && nhIt->hStart <= iSect)
            {
                toRemove.push_back(*hIt);
                hIt = nhIt;
                continue;
            }
            break;
        }

        if (newRh <= nextRh)
        {
            for (const auto& item : toRemove)
            {
                hSet.erase(item);
                hStartSet.erase(item);
            }
            if (hIt != hSet.end())
            {
                Item updatedItem = *hIt;
                hSet.erase(updatedItem);
                hStartSet.erase(updatedItem);
                updatedItem.hStart = nextRh;
                hSet.insert(updatedItem);
				hStartSet.insert(updatedItem);
            }
            newItem.hStart = newRh;
            hSet.insert(newItem);
			hStartSet.insert(newItem);
        }

        // let's do it again
		toRemove.clear();

        Rational newRw(0, 1);
        auto wIt = wSet.upper_bound(newItem);

        auto wprev = wIt;
        while(wprev != wSet.begin())
        {
            --wprev;
            if (wprev->w == newItem.w)
            {
                toRemove.push_back(*wprev);
                continue;
            }

            Rational iSect = Rational(wprev->score - newItem.score, newItem.w - wprev->w);
            if (iSect <= wprev->wStart)
            {
                toRemove.push_back(*wprev);
                continue;
            }
            else
            {
                newRw = iSect;
                break;
			}
        }

        Rational nextRw(1, 0);
        while (wIt != wSet.end())
        {
            if (wIt->w == newItem.w)
            {
                nextRw = Rational(0, 1);
                break;
            }
            Rational iSect = Rational(wIt->score - newItem.score, newItem.w - wIt->w);
            nextRw = iSect;
            auto nwIt = std::next(wIt);
            if (nwIt != wSet.end() && nwIt->wStart <= iSect)
            {
                toRemove.push_back(*wIt);
                wIt = nwIt;
                continue;
            }
            break; 
        }

        if (newRw <= nextRw)
        {
            for (const auto& item : toRemove)
            {
                wSet.erase(item);
                wStartSet.erase(item);
            }
            if (wIt != wSet.end())
            {
                Item updatedItem = *wIt;
                wSet.erase(updatedItem);
                wStartSet.erase(updatedItem);
                updatedItem.wStart = nextRw;
                wSet.insert(updatedItem);
				wStartSet.insert(updatedItem);
            }
            newItem.wStart = newRw;
            wSet.insert(newItem);
			wStartSet.insert(newItem);
        }       
    }

    return dp[n];
}

long long solve(std::vector<int> H, std::vector<int> W)
{
    int n = (int)H.size();
    std::vector<int64_t> h(H.begin(), H.end());
    std::vector<int64_t> w(W.begin(), W.end());
    int64_t maxh = 0;
    int maxhidx = -1;
    for (int i = 0; i < n; i++)
    {
        if (h[i] > maxh)
        {
            maxh = h[i];
            maxhidx = i;
        }
    }
    std::vector<int64_t> roth(n);
    std::vector<int64_t> rotw(n);
    for (int i = 0; i < n; i++)
    {
        int idx = (maxhidx + i) % n;
        roth[i] = h[idx];
        rotw[i] = w[idx];
    }

    int64_t opt1 = solve(roth, rotw);

    for (int i = 0; i < n; i++)
    {
        int idx = (maxhidx + n - i) % n;
        roth[i] = h[idx];
        rotw[i] = w[idx];
    }
    int64_t opt2 = solve(roth, rotw);

    return std::max(opt1, opt2);
}
