← 返回题目列表

Codeforces · 573/D

D. 熊和骑兵

中文机器翻译题面 查看原题

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

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。