CF573D.Bear and Cavalry

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 w__i and i-th horse has strength h__i. 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.

你愿意与骑马的熊作战吗？我也不愿意。

Limak 是一只灰熊，也是恐怖的熊国军队的统帅。而一支军队中最重要的部分，当然是骑兵。

熊国的骑兵由 $n$ 名战士和 $n$ 匹马组成。第 $i$ 名战士的力量为 $w_i$，第 $i$ 匹马的力量为 $h_i$。一名战士与其所骑的马合称为一个“单位”，一个单位的力量等于该战士与该马力量的乘积。整支骑兵的总力量等于所有 $n$ 个单位力量之和。优秀的战士与马的匹配方式能使骑兵真正强大。

初始时，第 $i$ 名战士骑的是第 $i$ 匹马。现在给出 $q$ 个查询，每次查询中两名战士交换各自所骑的马。

统帅 Limak 必须为一切可能的情况做好准备。例如：如果规定战士不得骑自己原本的马，那该怎么办？在每次查询之后，请计算骑兵可能达到的最大总力量——即在所有满足“没有战士被分配到其初始对应马匹”的战士与马的匹配方案中，总力量的最大值（可以证明：当 $n \geq 2$ 时，这样的合法匹配方案至少存在一种）。

注意：我们不能让任何一名战士没有马可骑。

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, _w_1, _w_2, ..., w__n (1 ≤ w__i ≤ 106) — strengths of warriors.

The third line contains n space-separated integers, _h_1, _h_2, ..., h__n (1 ≤ h__i ≤ 106) — strengths of horses.

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

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

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

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

接下来 $q$ 行描述查询。其中第 $i$ 行包含两个用空格分隔的整数 $a_i$ 和 $b_i$（$1 \leq a_i,\,b_i \leq n$，$a_i \neq b_i$），表示交换彼此战马的两名战士的下标。

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

输出 q 行，每行对应一个查询的答案。在第 i 行中，输出前 i 个查询之后骑兵可能达到的最大战斗力。

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.

第一个样例的说明：

战士：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$。