Let's model the problem as a graph problem. In this graph, each line in the $$$2D$$$ plane passing through the origin represents a node.

Now, for every point $$$P(x, y)$$$, it can either move to $$$P_{1}(x+1, y)$$$ or $$$P_{2}(x, y+1)$$$. Say the lines passing from the origin to these two points are $$$L_1$$$ and $$$L_2$$$ respectively.

If you assume the point $$$P$$$ moves to $$$P_1$$$ you can add an edge from $$$L_2$$$ to $$$L_1$$$ in our graph otherwise if the point $$$P$$$ moves to $$$P_2$$$, you add an edge from $$$L_1$$$ to $$$L_2$$$ in the graph. The point can also not move at all, but we will ignore this case (it will be clear why it won't matter).

Now, observe that, for each line $$$L$$$, we can pick the edges directed to $$$L$$$ and pair them (these edge-pairs will form point-pairs in our original problem, since each point corresponds to exactly one edge).

Note that if in-degree of $$$L$$$ is odd, then one incoming edge will be left without a pair. It's clear that we have to direct each edge in such a way that minimum number of nodes are left with odd in-degree.

Here comes the idea for the optimal solution: Initially, direct each edge arbitrary. While there are two nodes $$$L_1$$$ and $$$L_2$$$ having odd degree, such that they are in the same connected component (considering undirected version of the graph), consider any path between them and reverse all its edges.

Why is this optimal? How will you simulate the whole thing fast?

#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define priority_queue < ll, std::vector<ll>, std::greater<ll> > mnheap;    // mnheap.push(), mnheap.top(), mnheap.pop()
#define REP(i,a,b) for (auto i = a; i != b; i++)
#define ll long long int
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second
#define pb push_back
#define SQ(a) (a)*(a)
 
using namespace std;
            
        
void read(int n,vector<int>& x)
{
    x.clear();
    x.resize(n);
    for(int i = 0;i<n;i++)
    {
        cin>>x[i];
    }
    
}
void read(int n,int m,vector<vector<int>>& x)
{
    x.clear();
    x.resize(n,vector<int>(m));
    for(int i = 0;i<n;i++)
    {
        for(int j = 0 ;j<m;j++)
            cin>>x[i][j];
    }
}
void read(int n,vector<vector<int>>& x)
{
    x.clear();
    x.resize(n+1);
    for(int i = 0;i<n-1;i++)
    {
         int a,b;
         cin>>a>>b;
         x[a].pb(b);
         x[b].pb(a);
    }
}
void read(int n,vector<vector<int>>& x,int m)
{
    x.clear();
    x.resize(n+1);
    for(int i = 0;i<m;i++)
    {
         int a,b;
         cin>>a>>b;
         x[a].pb(b);
         x[b].pb(a);
    }
}
void read(int n,vector<ll>& x)
{
    x.clear();
    x.resize(n);
    for(int i = 0;i<n;i++)
    {
        cin>>x[i];
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    int T = 1;
    // cin>>T;
    
    for(int t = 1;t<=T;t++)
    {
        // cout<<"Case #"<<t<<": ";
        int n;
		cin>>n;
		vector<ll> a(n);
		vector<ll> b(n);
		read(n,a);
		read(n,b);
		vector<vector<ll>> mul(2*n);
		// vector<vector<ll>> pref(2*n);
		vector<ll> pref1(n);
		for(int i = 0;i<n;i++){
			if(i == 0){
				pref1[i] = a[i]*b[i];
			}
			else{
				pref1[i] = pref1[i-1] + a[i]*b[i];
			}
		}
		for(int i = 0;i<n;i++){
			for(int j = 0;j<n;j++){
				mul[i+j].pb(a[i]*b[j]);
			}
		}
		for(int i = 0;i<mul.size();i++){
			reverse(all(mul[i]));
			for(int j = 0;j<mul[i].size();j++){
				if(j == 0){
					continue;
				}
				else{
					mul[i][j] += mul[i][j-1];
				}
				// cout<<mul[i][j]<<" ";
			}
			// mul[i].clear();
			// cout<<endl;
		}
		ll bestsum = pref1[n-1];
		ll sum = pref1[n-1];
		ll diff = 0;
		// for(int i = 0;i<pref1.size();i++){
		// 	cout<<pref1[i]<<" ";
		// }
		// cout<<endl;
		ll x = 0;
		ll y = 0;
		ll z = 0;
		for(int i = 0;i<n;i++){
			for(int j = i+1;j<n;j++){
				
				if(i == 0)
					x = pref1[j];
				else{
					x = pref1[j] - pref1[i-1];
				}
				// ll y = 0;
				if(i+j < n){
					if(i == 0){
						y = mul[i+j][j];
					}
					else{
						y = mul[i+j][j] - mul[i+j][i-1];
					}
				}
				else{
					z = i+j - n + 1;
					if(i == z){
						y = mul[i+j][j-z];
					}
					else{
						y = mul[i+j][j-z] - mul[i+j][i-z-1];
					}
				}
				diff = max(diff,y-x);
			}
		}
		cout<<bestsum + diff<<endl;

    }

    return 0;
}