你想和骑着马的熊战斗吗?我也不。
Limak 是一只灰熊。他是可怕的熊地军队的将军。军队中最重要的部分当然是骑兵。
熊地骑兵由n名战士和n名马组成。第 i 个战士的力量为 wi,第 i 个马的力量为 hi。战士和他的马一起被称为一个单位。一个单位的力量等于战士和马的力量的乘积。骑兵的总兵力等于所有n个单位兵力的总和。兵马调配得当,骑兵才真正强大。
最初,第 i 个战士拥有第 i 匹马。您将收到 q 个查询。在每个查询中,两名战士互相交换马匹。
利马克将军必须为各种可能的情况做好准备。如果战士不被允许骑自己的马怎么办?在每次查询后,如果我们考虑将所有战士分配给所有马匹,并且没有战士分配给自己的马(可以证明,对于n≥2,总是至少有一个正确的分配),则找到骑兵的最大可能力量。
请注意,我们不能让战士没有马。
输入
第一行包含两个空格分隔的整数 n 和 q (2 ≤ n ≤ 30 000, 1 ≤ q ≤ 10 000)。
第二行包含 n 个空格分隔的整数,w1, w2, ..., wn (1 ≤ wi ≤ 106) — 战士的力量。
第三行包含 n 个空格分隔的整数,h1, h2, ..., hn (1 ≤ hi ≤ 106) — 马的强度。
接下来 q 行描述查询。其中第 i 个包含两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi),这是互相交换马匹的战士的索引。
输出
打印 q 行以及查询答案。在第 i 行中,在第 i 个查询后打印骑兵的最大可能强度。
示例
输入 #1
4 2 1 10 100 1000 3 7 2 5 2 4 2 4
输出 #1
5732 7532
输入 #2
3 3 7 11 5 3 2 1 1 2 1 3 2 3
输出 #2
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
输出 #3
9315 9308 9315 9315
注意
第一个样本的澄清:
战士:1 10 100 1000匹马: 3 7 2 5
第一次查询后情况如下所示:
勇士:1 10 100 1000匹马: 3 5 2 7
我们可以得到 1·2 + 10·3 + 100·7 + 1000·5 = 5732(请注意,在此任务中没有骠骑兵带着自己的马)。
第二次查询后,我们回到初始情况,最佳分配是 1·2 + 10·3 + 100·5 + 1000·7 = 7532。
第二个示例的澄清。第一次查询后:
战士: 7 11 5马匹: 2 3 1
最佳分配是 7·1 + 11·2 + 5·3 = 44。
第二次查询后 7·3 + 11·2 + 5·1 = 48。
最后 7·2 + 11·3 + 5·1 = 52。