题目描述

有 $n$ 个人和 $n$ 匹马，第 $i$ 个人对应第 $i$ 匹马。第 $i$ 个人能力值 $w_i$，第 $i$ 匹马能力值 $h_i$，第 $i$ 个人骑第 $j$ 匹马的总能力值为 $w_i\times h_j$，整个军队的总能力值为 $\sum w_i\times h_j$（一个人只能骑一匹马，一匹马只能被一个人骑）。

有一个要求：每个人都不能骑自己对应的马。让你制定骑马方案，使得整个军队的总能力值最大。现在有 $q$ 个操作，每次给出 $a,b$，交换 $a$ 和 $b$ 对应的马。每次操作后你都需要输出最大的总能力值。

输入格式

第一行两个整数 $n,q$，$2\le n\le 30000$，$1\le q\le 10000$。

第二行 $n$ 个整数 $w_i$，$1\le w_{i}\le 10^{6}$。

第三行 $n$ 个整数 $h_i$，$1\le h_{i}\le 10^{6}$。

接下来 $q$ 行，每行两个整数 $a_i,b_i$，表示询问，$1\le a_{i},b_{i}\le n$，$a_{i}≠b_{i}$。

输出格式

对于每个询问，在一行中输出一个整数表示答案。

4 2
1 10 100 1000
3 7 2 5
2 4
2 4

5732
7532

3 3
7 11 5
3 2 1
1 2
1 3
2 3

44
48
52

7 4
1 2 4 8 16 32 64
87 40 77 29 50 11 18
1 5
2 7
6 2
5 6

9315
9308
9315
9315