D. 熊与骑兵
每次测试的时间限制：3 秒
每次测试的内存限制：256 兆字节

你想和骑着马的熊战斗吗？我也不想。

$Limak$ 是一头灰熊。他是熊国可怕军队的将军。军队中最重要的部分当然是骑兵。

熊国骑兵由 $n$ 名战士和 $n$ 匹马组成。第 $i$ 名战士的力量为 $w_i$，第 $i$ 匹马的力量为 $h_i$。战士与他的坐骑一起被称为一个单位。一个单位的力量等于战士力量与马力量的乘积。骑兵的总力量等于所有 $n$ 个单位力量的总和。战士与马的良好分配能使骑兵真正强大。

最初，第 $i$ 名战士拥有第 $i$ 匹马。你会得到 $q$ 个查询。在每个查询中，两名战士互相交换他们的马。

将军 $Limak$ 必须为每一种可能的情况做好准备。如果战士不被允许骑自己的马，那该怎么办？在每次查询后，找出在所有战士分配到所有马且没有战士被分配到他自己的马的分配中，骑兵可能的最大总力量（可以证明对于 $n \ge 2$，至少存在一种正确的分配）。

注意，我们不能让任何战士没有马。

---

输入
第一行包含两个空格分隔的整数 $n$ 和 $q$（$2 \le n \le 30\,000$，$1 \le q \le 10\,000$）。

第二行包含 $n$ 个空格分隔的整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10^6$）—— 战士的力量。

第三行包含 $n$ 个空格分隔的整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 10^6$）—— 马的力量。

接下来的 $q$ 行描述查询。第 $i$ 行包含两个空格分隔的整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），即交换马的战士的编号。

---

输出
输出 $q$ 行，每行一个查询的答案。在第 $i$ 行中，输出前 $i$ 次查询后骑兵的最大可能总力量。

---

示例

示例 1
输入

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

输出

5732
7532

示例 2
输入

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

输出

44
48
52

示例 3
输入

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

输出

9315
9308
9315
9315

注释
第一个示例的解释：

战士：$1\ 10\ 100\ 1000$
马：$3\ 7\ 2\ 5$

第一次查询后的情况：

战士：$1\ 10\ 100\ 1000$
马：$3\ 5\ 2\ 7$

我们可以得到 $1\cdot2 + 10\cdot3 + 100\cdot7 + 1000\cdot5 = 5732$（注意在这个分配中没有战士骑自己的马）。

第二次查询后回到初始情况，最优分配是 $1\cdot2 + 10\cdot3 + 100\cdot5 + 1000\cdot7 = 7532$。

第二个示例的解释：第一次查询后：

战士：$7\ 11\ 5$
马：$2\ 3\ 1$

最优分配是 $7\cdot1 + 11\cdot2 + 5\cdot3 = 44$。

第二次查询后：$7\cdot3 + 11\cdot2 + 5\cdot1 = 48$。

第三次查询后：$7\cdot2 + 11\cdot3 + 5\cdot1 = 52$。