You are given two integer arrays a and b of length n.

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

Your task is to reverse such a subarray that the sum ∑_{i=1}^n a_i ⋅ b_i is maximized.

Input

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

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^7).

The third line contains n integers b_1, b_2, ..., b_n (1 ≤ b_i ≤ 10^7).

Output

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

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]. Then a = [2, 3, 2, 3, 1] and 2 ⋅ 1 + 3 ⋅ 3 + 2 ⋅ 2 + 3 ⋅ 4 + 1 ⋅ 2 = 29.

In the second example, you don't need to use the reverse operation. 13 ⋅ 2 + 37 ⋅ 4 = 174.

In the third example, you can reverse the subarray [3, 5]. Then a = [1, 8, 3, 6, 7, 6] and 1 ⋅ 5 + 8 ⋅ 9 + 3 ⋅ 6 + 6 ⋅ 8 + 7 ⋅ 8 + 6 ⋅ 6 = 235.
#include <algorithm>
#include <array>
#include <cmath>
#include <functional> 
#include <iostream>
#include <memory>
#include <numeric>
#include <queue>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>

namespace predefined {

#ifdef CODEFORCES_DEBUG
  constexpr bool kIsDebug = true;
#else
  constexpr bool kIsDebug = false;
#endif

enum class LogType {
  INFO,
  DEBUG
};

template <LogType Type, bool... Bools>
struct Log;

template <>
struct Log<LogType::INFO> {
  Log() {}
  ~Log() { std::cout << '\n'; }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, true>{
  Log() {}
  ~Log() { std::cout << '\n'; }

  void Open() {
    freopen("input.txt", "r", stdin);
  }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, false> {
  Log() {}
  ~Log() {}

  void Open() {}

  template <typename T>
  Log& operator<< (const T &t) { return *this; }
};

namespace solver {

template <class Arg>
void GetArg(Arg& value) {
  std::cin >> value;
}

template <size_t index, class... Args>
typename std::enable_if<index == sizeof...(Args)>::type
GetArgsImpl(std::tuple<Args...>& args) {}

template <size_t index, class... Args>
typename std::enable_if<(index < sizeof...(Args))>::type
GetArgsImpl(std::tuple<Args...>& args) {
  GetArg(std::get<index>(args));
  GetArgsImpl<index + 1>(args);
}

template<typename ... Args>
std::tuple<Args...> GetArgs() {
  std::tuple<Args...> args;

  GetArgsImpl<0>(args);

  return args;
}

template<int...> struct IndexTuple {};

template<int I, typename T, typename... Types> 
struct MakeIndexesImpl; 

template<int I, int... Indexes, typename T, typename ... Types> 
struct MakeIndexesImpl<I, IndexTuple<Indexes...>, T, Types...> 
{ 
  typedef typename MakeIndexesImpl<I + 1, IndexTuple<Indexes..., I>, Types...>::type type; 
};

template<int I, int... Indexes> 
struct MakeIndexesImpl<I, IndexTuple<Indexes...> > 
{ 
  typedef IndexTuple<Indexes...> type; 
};

template<typename ... Types> 
struct MakeIndexes : MakeIndexesImpl<0, IndexTuple<>, Types...> 
{};

template<class... Args, int... Indexes > 
void RunImpl(void (*func)(Args...), std::tuple<Args...>&& args, IndexTuple< Indexes... >) 
{ 
  func(std::forward<Args>( std::get<Indexes>(args))... ); 
} 

template<class ... Args> 
void RunImpl(void (*func)(Args...), const std::tuple<Args...>& args) {
  RunImpl(func, std::tuple<Args...>(args), typename MakeIndexes<Args...>::type());
}

template<typename ... Args>
void Run(void (*func)(Args...)) {
  std::tuple<Args...> args = GetArgs<Args...>();

  RunImpl(func, args);;
}

template <typename T>
std::size_t GetTestCaseCount();

template <>
std::size_t GetTestCaseCount<std::true_type>() {
  std::size_t test_case_count;
  std::cin >> test_case_count;
  return test_case_count;
}

template <>
std::size_t GetTestCaseCount<std::false_type>() {
  return 1;
}

} // solver

template <bool MultiTest>
struct Solver {
  constexpr static bool condition = MultiTest | kIsDebug;
  typedef typename std::conditional<condition, std::true_type, std::false_type>::type run_type;

  template <typename ... Args>
  static void Run(void (*func)(Args...)) {
    auto tc_count = solver::GetTestCaseCount<run_type>();
    while (tc_count--) solver::Run(func);
  }
};

template<typename T>
struct BoolMap {
  explicit BoolMap(const T &_true_value, const T &_false_value) 
      : true_value(_true_value),
        false_value(_false_value) {}

  const T inline GetValue(const bool bool_key) const {
    return bool_key ? true_value : false_value;  
  };

  const T true_value;
  const T false_value;
};

}  // predefined;

#define LOGI predefined::Log<predefined::LogType::INFO>()
#define LOGD predefined::Log<predefined::LogType::DEBUG, predefined::kIsDebug>()
#define LABEL(variable_name) #variable_name << ": " << variable_name << " "

#define INIT_ANSWER(type, true_value, false_value) \
  const predefined::BoolMap<type> predefined_bool_map(true_value, false_value)
#define INIT_STRING_ANSWER(true_string, false_string) \
  INIT_ANSWER(std::string, true_string, false_string)
#define GET_ANSWER(bool_key) \
  predefined_bool_map.GetValue(bool_key)

#define INIT_CODEFORCES() \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(NULL); \
  LOGD.Open();

namespace {
using namespace std;

constexpr bool kMultiTestCase = false;
using Solver = predefined::Solver<kMultiTestCase>;

constexpr int kInf = 0x7FFFFFFF;
}  // unnamed namespace;

void solve(int n) {
  vector<long long> a(n), b(n);
  
  for (auto &ai : a) {
    cin >> ai;
  }

  for (auto &bi : b) {
    cin >> bi;
  }

  long long ans = 0;
  long long base = 0;

  vector<long long> verse(n);
  for (int i = 0; i < n; ++i) {
    verse[i] = a[i] * b[i];
    base += verse[i];
  }

  ans = base;
  for (int i = 0; i < n; ++i) {
    int cnt = min(i - 0, n - 1 - i);
    long long now = base;
    for (int j = 1; j <= cnt; j++) {
      now -= verse[i - j];
      now -= verse[i + j];
      now += a[i + j] * b[i - j];
      now += a[i - j] * b[i + j];

      ans = max(ans, now);
    }
  }

  for (int i = 0; i < n - 1; ++i) {
    int cnt = min(i - 0, n - 2 - i);
    long long now = base;
    now -= verse[i];
    now -= verse[i + 1];
    now += a[i] * b[i + 1];
    now += a[i + 1] * b[i];
    ans = max(ans, now);

    for (int j = 1; j <= cnt; j++) {
      now -= verse[i - j];
      now -= verse[i + 1 + j];
      now += a[i + 1 + j] * b[i - j];
      now += a[i - j] * b[i + 1 + j];
      ans = max(ans, now);
    }
  }

  LOGI << ans;
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver::Run(&solve);

  return 0;
}
