# [SOLUTION] Maximum Sum of Products solution codeforces – You are given two integer arrays aa and bb of length nn. 2021

## Maximum Sum of Products solution codeforces

You are given two integer arrays aa and bb of length nn.

You can reverse at most one subarray (continuous subsegment) of the array aa.

Your task is to reverse such a subarray that the sum i=1naibi∑i=1nai⋅bi is maximized.

Input :

The first line contains one integer nn (1n50001≤n≤5000).

The second line contains nn integers a1,a2,,ana1,a2,…,an (1ai1071≤ai≤107).

The third line contains nn integers b1,b2,,bnb1,b2,…,bn (1bi1071≤bi≤107).

Output :

Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of aa.

Examples

input

5
2 3 2 1 3
1 3 2 4 2


output

29


input

2
13 37
2 4


output

174


input

6
1 8 7 6 3 6
5 9 6 8 8 6


output

235

Note

In the first example, you can reverse the subarray [4,5][4,5]. Then a=[2,3,2,3,1]a=[2,3,2,3,1] and 21+33+22+34+12=292⋅1+3⋅3+2⋅2+3⋅4+1⋅2=29.

In the second example, you don’t need to use the reverse operation. 132+374=17413⋅2+37⋅4=174.

In the third example, you can reverse the subarray [3,5][3,5]. Then a=[1,8,3,6,7,6]a=[1,8,3,6,7,6] and 15+89+36+68+78+66=2351⋅5+8⋅9+3⋅6+6⋅8+7⋅8+6⋅6=235.

## C++

#include<bits/stdc++.h>
#define F(i,l,r)for(i=l;i<=r;i++)
using namespace std;int64_t a[1<<13],b[1<<13],t[1<<15],n,m,p,i,j;int main(){cin>>n;
F(i,1,n)cin>>a[i];
F(i,1,n)cin>>b[i],p=m+=a[i]*b[i];
F(i,2,n)F(j,1,i-1)t[i+j]+=(a[i]-a[j])*(b[j]-b[i]),m=max(m,p+t[i+j]);cout<<m;
}

## JAVA

import java.io.IOException;
import java.util.*;

import java.math.*;
import java.io.*;
import java.text.*;
import java.math.BigInteger;
public class Main {

static class pair{
int x;
int y;
public pair(int a,int b) {
this.x=a;
this.y=b;
}
}
public static boolean[] sieve(long n)
{
boolean[] prime = new boolean[(int)n+1];
Arrays.fill(prime,true);
prime[0] = false;
prime[1] = false;
long m = (long)Math.sqrt(n);
for(int i=2;i<=m;i++)
{
if(prime[i])
{
for(int k=i*i;k<=n;k+=i)
{
prime[k] = false;
}
}
}
return prime;
}

public static boolean[] primeseive(long n) {
boolean prime[]=new boolean[(int)n+1];

Arrays.fill(prime, true);

prime[0]=false;
prime[1]=false;

int m=(int) Math.sqrt(n);

for(int i=2;i<m;i++) {
if(prime[i]) {

for(int k=i*i;k<=n;k+=i) {
prime[k]=false;
}
}
}

return prime;
}

static long GCD(long a,long b)
{
if(b==0)
{
return a;
}
return GCD(b,a%b);
}

static long gcdnik(long a,long b)
{
if(b==0)
{
return a;
}
return GCD(b,a%b);
}

static long CountCoPrimes(long n)
{
long res = n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
while(n%i==0)
{
n/=i;
}
res-=res/i;
}
}
if(n>1)
{
res-=res/n;
}
return res;
}

static boolean prime(int n)
{
for(int i=2;i*i<=n;i++)
{
if(i%2==0 ||i%3==0)
{
return false;
}
}
return true;
}
static String userIdGeneration(String input1,String input2,int input3,int input4) {
if(input1.length()==input2.length()) {
String arr[]=new String[2];

arr[0]=input1;
arr[1]=input2;

Arrays.sort(arr);
char c=arr[0].charAt(0);
String output=c+arr[1];

String k=Integer.toString(input3);

char d=k.charAt(input4-1);

output+=d;

char e=k.charAt(k.length()-input4);
output+=e;
String res="";
for(int i=0;i<output.length();i++) {
if(Character.isUpperCase(output.charAt(i))){
res+=Character.toLowerCase(output.charAt(i));
}
else {
res+=Character.toUpperCase(output.charAt(i));
}
}
return res;
}

else {
String arr[]=new String[2];
arr[0]=input1.length()>input2.length()?input2:input1;
arr[1]=input1.length()>input2.length()?input1:input2;

char c=arr[0].charAt(0);

String output=c+arr[1];

String k=Integer.toString(input3);

char d=k.charAt(input4-1);

output+=d;

char e=k.charAt(k.length()-input4);
output+=e;
String res="";
for(int i=0;i<output.length();i++) {
if(Character.isUpperCase(output.charAt(i))){
res+=Character.toLowerCase(output.charAt(i));
}
else {
res+=Character.toUpperCase(output.charAt(i));
}
}
return res;
}

}
static int length(int len) {

if(len==1) {
return 1;
}
else if(len==2) {
return 3;
}
else if(len==3) {
return 6;
}
else if(len==4) {
return 10;
}
return 0;
}

public static int LargestFour(int arr[]) {
Arrays.sort(arr);

int n=arr.length;
int count=0;
int sum=0;
for(int i=n-1;i>=1;i--) {
sum+=arr[i];

count++;
if(count==4) {
break;

}

}

if(count<4) {
sum+=arr[0];
}

return sum;
}
//Nikunj Gupta
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
}

static String solve23(int n) {
int k=0;
while(true) {
if(n-2020*k<0) {
return "NO";
}
if((n-2020*k)%2021==0) {
return "YES";
}
k++;
}

}

static void solve(int n,int k) {

if(n==1) {
System.out.println(0);
return;
}
int p=(k+1)/2;

System.out.println((k-p)+(n-k));

for(int j=p;j<k;j++) {
System.out.print(j+" ");
}
for(int j=k+1;j<=n;j++) {
System.out.print(j+" ");
}

System.out.println();
}

static int row[]= {1,0};
static int col[]= {0,1};
static ArrayList<String>l=new ArrayList<>();
public static void main(String[] args) throws IOException{

Scanner s=new Scanner(System.in);

// int op=s.nextInt();

long mod=1000000007;

int n=s.nextInt();

long arr[]=new long[n];
long arr1[]=new long[n];
for(int i=0;i<n;i++) {
arr[i]=s.nextLong();
}
for(int j=0;j<n;j++) {
arr1[j]=s.nextLong();
}
long total=0;

long dp[]=new long[n];
for(int i=0;i<n;i++) {

total+=arr[i]*arr1[i];
dp[i]=arr[i]*arr1[i];
}
long max=total;
// System.out.println(total);

for(int i=0;i<n;i++) {
int l=i-1;
int r=i+1;
long ans=total;
while(l>=0&&r<n) {
ans-=(arr[l]*arr1[l]+arr[r]*arr1[r]);
ans+=(arr[l]*arr1[r]+arr[r]*arr1[l]);
l--;
r++;
max=Math.max(ans,max);
}

}
for(int i=0;i<n;i++) {
int l=i;
int r=i+1;
long ans=total;
while(l>=0&&r<n) {
ans-=(arr[l]*arr1[l]+arr[r]*arr1[r]);
ans+=(arr[l]*arr1[r]+arr[r]*arr1[l]);
l--;
r++;
max=Math.max(ans,max);
}

}
System.out.println(max);

}

private static void printsubsequences(String c, String st) {
// TODO Auto-generated method stub

if(c.length()==0) {
System.out.println(st);
return;
}

printsubsequences(c.substring(1),st+c.charAt(0));
printsubsequences(c.substring(1),st);

}

private static boolean compare(HashMap<Character, Integer> smap, HashMap<Character, Integer> pmap) {
// TODO Auto-generated method stub

for(char ch:smap.keySet()) {
if(smap.get(ch)!=pmap.get(ch)) {
return false;
}
}
return true;
}

private static boolean BinarySearch(int search, int[] val, int n)
{
// TODO Auto-generated method stub

int start=0;
int end=val.length-1;
while(start<=end) {
int mid=(start+end)/2;

if(val[mid]==search) {
return true;
}
else if(val[mid]<search) {
start=mid+1;
}
else {
end=mid-1;
}

}
return false;
}

static long findGCD(ArrayList<Long> arr,long start, long n)
{
long result = arr.get((int)start);
for (int i = (int)start+1; i < n; i++)
result = GCD(arr.get(i), result);

return result;
}

static long re(long n)
{
n+=1;
while(n%10==0)
{
n/=10;
}
return n;
}

//xor range query
static long xor(long n)
{

if(n%4==0)
{
return n;
}
if(n%4==1)
{
return 1;
}
if(n%4==2)
{
return n+1;
}
return 0;
}

static long xor(long a,long b)
{
return xor(b)^xor(a-1);
}

static void swap(char c,char p)
{
char t = c;
c = p;
p = t;
}

static long max(long n,long m)
{
return Math.max(n,m);
}
static long min(long n,long m)
{
return Math.min(n,m);
}

// double nd() throws IOException
// {
// return Double.parseDouble(in.next());
// }
// int ni() throws IOException
// {
// return Integer.parseInt(in.next());
// }
//
// long nl() throws IOException
// {
// return Long.parseLong(in.next());
// }
//
// String si() throws IOException
// {
// return in.next();
// }
//
//

static int abs(int n)
{
return Math.abs(n);
}

static class Scanner
{
StringTokenizer st;

public String next() throws IOException
{
while (st == null || !st.hasMoreTokens())
{
}
return st.nextToken();
}

public int nextInt() throws IOException {return Integer.parseInt(next());}

public long nextLong() throws IOException {return Long.parseLong(next());}

public String nextLine() throws IOException {return br.readLine();}

}

}

class Pair implements Comparable<Pair>
{
int x,y;
public Pair(int x,int y)
{
this.x = x;
this.y = y;
}
public int compareTo(Pair o)
{
return this.y-o.y;
}
}



## KOTLIN

import kotlin.math.max

fun main() {
val ay = readLine()!!.split(" ").map { it.toLong() }
val by = readLine()!!.split(" ").map { it.toLong() }
val dp = Array(n) { LongArray(n) }
for (x in n - 1 downTo 0) {
for (y in x + 1 until n) {
dp[x][y] = ((ay[x] - ay[y]) * (by[y] - by[x])) + dp[x + 1][y - 1]
}
}
for (x in 0 until n) {
}
}

## GO

package main
import("bufio";."fmt";"os")

func main() {
n,s:=0,int64(0)
Fscan(in,&n)
a:=make([][2]int64,n)
for i:= range a{Fscan(in,&a[i][0])}
for i:= range a{Fscan(in,&a[i][1]); s+=a[i][0]*a[i][1]}
c := make([]int64, 2*n)
ans := s
for i, p := range a {
for j, q := range a[:i] {
if c[i+j]-=(p[0]-q[0])*(p[1]-q[1]); s+c[i+j]>ans {
ans=s+c[i+j]
}
}
}
Print(ans)
}

## PYTHON

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for i in range(n):
ans += a[i] * b[i]
base = ans
for i in range(n):
for j in (i - 1, i):
cur = base
k = i + 1
while j >= 0 and k < n:
cur -= (a[j] - a[k]) * (b[j] - b[k])
ans = max(ans, cur)
j -= 1
k += 1
print(ans)

Maximum Sum of Products solution codeforces, Maximum Sum of Products solution codeforces 2021, Maximum Sum of Products solution codeforces , Maximum Sum of Products solution codeforces 2021 , Maximum Sum of Products solution codeforces, Maximum Sum of Products solution codeforces 2021, Maximum Sum of Products solution codeforces , Maximum Sum of Products solution codeforces 2021 , Maximum Sum of Products solution codeforces, Maximum Sum of Products solution codeforces 2021, Maximum Sum of Products solution codeforces , Maximum Sum of Products solution codeforces 2021 ,  , Maximum Sum of Products solution codeforces 2021, Maximum Sum of Products solution codeforces , Maximum Sum of Products solution codeforces 2021 ,