运气大战

你的班上$n$个同学要去参加一项集体比赛。每个人有实力值和运气值。每个人的实力值是确定的，但是运气值是飘忽不定的。一个人的发挥是他的实力值$w_i$ 和运气值的乘积，即$w_i\cdot r_{c_i}$。班级的发挥是所有人发挥之和。每个人有一个初始运气值$r_i$，但是每次比赛的时候，每个人的运气值是所有人运气值的一个排列，并且要满足，排列之后$i$的运气值不是$r_i$。即满足，$i$的运气值是$r_{c_i}$，$\{c_i\}$是$1-n$的排列，且满足$c_i\not=i$。

现在有$Q$场比赛，每场比赛前会交换两人的初始运气值。问你每场比赛班级可以获得的最大发挥是多少。

输入格式

第一行两个整数 $n$ 和 $Q$。

第二行$n$个整数$w_1,...,w_n$。

第三行$n$个整数$r_1,...,r_n$。

接下来$Q$行，每行两个整数$a_i,b_i$表示每次要交换运气值的两个人的编号。

输出格式

共$Q$行，每行一个答案，表示这场比赛班级的最大发挥。

样例1

输入

5 5
25 1 16 26 19 
11 27 4 8 20 
1 5
1 5
2 5
1 2
5 4

输出

1527
1543
1543
1536
1536

样例2

点此下载

数据范围

20% $n\le 10,q\le 10$

另30% $n\le 1000,q\le 100$

另20% $n\le 30000,q\le 500$

100% $2\le n\le 30000,1\le q\le 10000,1\le w_i,r_i \le 1e6,1\le a_i\not=b_i \le n$