熊与骑兵

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

熊之国的骑兵有 $n$ 位勇士和 $n$ 匹马。第 $i$ 位勇士的力量为 $w_i$，第 $i$ 匹马的力量为 $h_i$。勇士与马组成的单位力量等于两者力量的乘积，骑兵总力量为所有单位力量之和。

初始时，第 $i$ 位勇士拥有第 $i$ 匹马。你将得到 $q$ 次操作，每次有两位勇士交换他们当前拥有的马。

每次操作后，需要重新将所有马一一分配给所有勇士，且任何勇士都不能骑自己当前拥有的马。请计算所有合法分配中可能达到的最大总力量。保证 $n\ge2$ 时总存在合法分配。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $w_1,w_2,\ldots,w_n$。

第三行 $n$ 个整数 $h_1,h_2,\ldots,h_n$。

接下来 $q$ 行，每行两个不同的整数 $a_i,b_i$，表示这两位勇士交换当前拥有的马。

输出格式

输出 $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

数据范围

$2\le n\le30000$，$1\le q\le10000$，$1\le w_i,h_i\le10^6$，$1\le a_i,b_i\le n$ 且 $a_i\ne b_i$。

每个测试点独立计分。