Problem: Would you want to fight against bears riding horses? Me neither.

Limak is a grizzly bear. He is general of the dreadful army of Bearland. The most important part of an army is cavalry of course.

Cavalry of Bearland consists of n warriors and n horses. i-th warrior has strength wi and i-th horse has strength hi. Warrior together with his horse is called a unit. Strength of a unit is equal to multiplied strengths of warrior and horse. Total strength of cavalry is equal to sum of strengths of all n units. Good assignment of warriors and horses makes cavalry truly powerful.

Initially, i-th warrior has i-th horse. You are given q queries. In each query two warriors swap their horses with each other.

General Limak must be ready for every possible situation. What if warriors weren't allowed to ride their own horses? After each query find the maximum possible strength of cavalry if we consider assignments of all warriors to all horses that no warrior is assigned to his own horse (it can be proven that for n ≥ 2 there is always at least one correct assignment).

Note that we can't leave a warrior without a horse.

Input

The first line contains two space-separated integers, n and q (2 ≤ n ≤ 30 000, 1 ≤ q ≤ 10 000).

The second line contains n space-separated integers, w1, w2, ..., wn (1 ≤ wi ≤ 106) — strengths of warriors.

The third line contains n space-separated integers, h1, h2, ..., hn (1 ≤ hi ≤ 106) — strengths of horses.

Next q lines describe queries. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), indices of warriors who swap their horses with each other.

Output

Print q lines with answers to queries. In i-th line print the maximum possible strength of cavalry after first i queries.

Examples

Input

4 2
1 10 100 1000
3 7 2 5
2 4
2 4


Output

5732
7532


Input

3 3
7 11 5
3 2 1
1 2
1 3
2 3


Output

44
48
52


Input

7 4
1 2 4 8 16 32 64
87 40 77 29 50 11 18
1 5
2 7
6 2
5 6


Output

9315
9308
9315
9315

Note

Clarification for the first sample:

Warriors: 1 10 100 1000

Horses: 3 7 2 5 

After first query situation looks like the following:

Warriors: 1 10 100 1000

Horses: 3 5 2 7 

We can get 1·2 + 10·3 + 100·7 + 1000·5 = 5732 (note that no hussar takes his own horse in this assignment).

After second query we get back to initial situation and optimal assignment is 1·2 + 10·3 + 100·5 + 1000·7 = 7532.

Clarification for the second sample. After first query:

Warriors: 7 11 5

Horses: 2 3 1

Optimal assignment is 7·1 + 11·2 + 5·3 = 44.

Then after second query 7·3 + 11·2 + 5·1 = 48.

Finally 7·2 + 11·3 + 5·1 = 52.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
int scan() { return getchar(); }
template <class T>
void scan(T a) {
  cin >> a;
}
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string &a) { cin >> a; }
template <class T>
void scan(vector<T> &);
template <class T, size_t size>
void scan(array<T, size> &);
template <class T, class L>
void scan(pair<T, L> &);
template <class T, size_t size>
void scan(T (&)[size]);
template <class T>
void scan(vector<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(deque<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T, size_t size>
void scan(array<T, size> &a) {
  for (auto &i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L> &p) {
  scan(p.first);
  scan(p.second);
}
template <class T, size_t size>
void scan(T (&a)[size]) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
  scan(head);
  IN(tail...);
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T, class S>
inline bool chmax(T &a, S b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T, class S>
inline bool chmin(T &a, S b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
template <class T>
void UNIQUE(vector<T> &x) {
  sort(begin(x), end(x));
  x.erase(unique(begin(x), end(x)), x.end());
}
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  unsigned long long x;
  cin >> x;
  return x;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string &a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T> &);
template <class T, size_t size>
void print(const array<T, size> &);
template <class T, class L>
void print(const pair<T, L> &p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T> &a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T> &a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size> &a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L> &p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T>
void print(set<T> &x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T>
void print(multiset<T> &x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T &a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T &t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head &head, const Tail &...tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
vector<pair<long long, long long>> factor(long long x) {
  vector<pair<long long, long long>> ans;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back({i, 1});
      while ((x /= i) % i == 0) ans.back().second++;
    }
  if (x != 1) ans.push_back({x, 1});
  return ans;
}
template <class T>
vector<T> divisor(T x) {
  vector<T> ans;
  for (T i = 1; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back(i);
      if (i * i != x) ans.push_back(x / i);
    }
  return ans;
}
template <typename T>
void zip(vector<T> &x) {
  vector<T> y = x;
  sort(begin(y), end(y));
  for (int i = 0; i < x.size(); ++i) {
    x[i] = distance((y).begin(), lower_bound(begin(y), end(y), (x[i])));
  }
}
int popcount(long long x) { return __builtin_popcountll(x); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int n) { return uniform_int_distribution<int>(0, n - 1)(rng); }
template <typename T>
void shuffle(vector<T> &v) {
  for (long long i = v.size() - 1; i >= 1; --i) {
    swap(v[i], v[rnd(i)]);
  }
}
vector<string> YES{"NO", "YES"};
vector<string> Yes{"No", "Yes"};
vector<string> yes{"no", "yes"};
template <class... T>
void err(const T &...) {}
template <typename T>
struct edge {
  int from, to;
  T cost;
  int id;
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
  edge(int from, int to, T cost, int id)
      : from(from), to(to), cost(cost), id(id) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
struct Graph : vector<vector<int>> {
  using vector<vector<int>>::vector;
  Graph(int n, int m) : vector(n) { read(m); }
  inline void add(int a, int b, bool directed = false) {
    (*this)[a].emplace_back(b);
    if (!directed) (*this)[b].emplace_back(a);
  }
  void read(int n = -1, int offset = 1, bool directed = false) {
    if (n == -1) n = this->size() - 1;
    int a, b;
    while (n--) {
      cin >> a >> b;
      Graph::add(a - offset, b - offset, directed);
    }
  }
};
template <typename T>
struct WeightedGraph : vector<Edges<T>> {
  using vector<Edges<T>>::vector;
  inline void add(int a, int b, T c, bool directed = false) {
    (*this)[a].emplace_back(b, c);
    if (!directed) (*this)[b].emplace_back(a, c);
  }
  void read(int n = -1, int offset = 1) {
    if (n == -1) n = this->size() - 1;
    int a, b;
    T c;
    while (n--) {
      cin >> a >> b >> c;
      WeightedGraph::add(a - offset, b - offset, c);
    }
  }
};
struct Setup_io {
  Setup_io() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
  }
} setup_io;
const int N = 30001;
long long dp[N], a[N], b[N];
int id[N];
long long d[N][4];
int main() {
  int n, Q;
  IN(n, Q);
  for (long long i = 0; i < n; ++i) cin >> a[i];
  for (long long i = 0; i < n; ++i) cin >> b[i];
  auto aid = iota(n), bid(iota(n));
  sort(begin(aid), end(aid), [&](int x, int y) { return a[x] < a[y]; });
  sort(begin(bid), end(bid), [&](int x, int y) { return b[x] < b[y]; });
  vector<int> reva(n), revb(n);
  for (long long i = 0; i < n; ++i) reva[aid[i]] = i, revb[bid[i]] = i;
  for (long long i = 0; i < n; ++i) id[i] = revb[aid[i]];
  sort(a, a + n), sort(b, b + n);
  constexpr long long inf = 1e18;
  auto calc = [&](int i) -> void {
    if (i < 0 or i > n - 1) return;
    if (id[i] != i)
      d[i][0] = a[i] * b[i];
    else
      d[i][0] = -inf;
    if (i < n - 1 and id[i] != i + 1 and id[i + 1] != i)
      d[i][1] = a[i] * b[i + 1] + a[i + 1] * b[i];
    else
      d[i][1] = -inf;
    if (i < n - 2 and id[i] != i + 2 and id[i + 1] != i and id[i + 2] != i + 1)
      d[i][2] = a[i] * b[i + 2] + a[i + 1] * b[i] + a[i + 2] * b[i + 1];
    else
      d[i][2] = -inf;
    if (i < n - 2 and id[i] != i + 1 and id[i + 1] != i + 2 and id[i + 2] != i)
      d[i][3] = a[i] * b[i + 1] + a[i + 1] * b[i + 2] + a[i + 2] * b[i];
    else
      d[i][3] = -inf;
  };
  for (long long i = 0; i < n; ++i) {
    calc(i);
  }
  while (Q--) {
    int x, y;
    IN(x, y);
    x--, y--;
    swap(id[reva[x]], id[reva[y]]);
    for (long long i = -3; i <= 3; ++i) calc(reva[x] + i), calc(reva[y] + i);
    for (long long i = 1; i <= n; ++i) dp[i] = -inf;
    for (long long i = 0; i < n; ++i) {
      chmax(dp[i + 1], dp[i] + d[i][0]);
      chmax(dp[i + 2], dp[i] + d[i][1]);
      chmax(dp[i + 3], dp[i] + d[i][2]);
      chmax(dp[i + 3], dp[i] + d[i][3]);
    }
    cout << dp[n] << '\n';
  }
}