You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Would you want to fight against bears riding horses? Me neither.

Limak is a grizzly bear. He is general of the dreadful army of Bearland. The most important part of an army is cavalry of course.

Cavalry of Bearland consists of n warriors and n horses. i-th warrior has strength wi and i-th horse has strength hi. Warrior together with his horse is called a unit. Strength of a unit is equal to multiplied strengths of warrior and horse. Total strength of cavalry is equal to sum of strengths of all n units. Good assignment of warriors and horses makes cavalry truly powerful.

Initially, i-th warrior has i-th horse. You are given q queries. In each query two warriors swap their horses with each other.

General Limak must be ready for every possible situation. What if warriors weren't allowed to ride their own horses? After each query find the maximum possible strength of cavalry if we consider assignments of all warriors to all horses that no warrior is assigned to his own horse (it can be proven that for n ≥ 2 there is always at least one correct assignment).

Note that we can't leave a warrior without a horse.

## Input Format
The first line contains two space-separated integers, n and q (2 ≤ n ≤ 30 000, 1 ≤ q ≤ 10 000).

The second line contains n space-separated integers, w1, w2, ..., wn (1 ≤ wi ≤ 106) — strengths of warriors.

The third line contains n space-separated integers, h1, h2, ..., hn (1 ≤ hi ≤ 106) — strengths of horses.

Next q lines describe queries. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), indices of warriors who swap their horses with each other.

## Output Format
Print q lines with answers to queries. In i-th line print the maximum possible strength of cavalry after first i queries.

## Examples
```input
4 2
1 10 100 1000
3 7 2 5
2 4
2 4
```
```output
5732
7532
```
-----
```input
3 3
7 11 5
3 2 1
1 2
1 3
2 3
```
```output
44
48
52
```
-----
```input
7 4
1 2 4 8 16 32 64
87 40 77 29 50 11 18
1 5
2 7
6 2
5 6
```
```output
9315
9308
9315
9315
```

## Note
Clarification for the first sample:

Warriors: 1 10 100 1000Horses:   3  7  2    5

After first query situation looks like the following:

Warriors: 1 10 100 1000Horses:   3  5  2    7

We can get 1·2 + 10·3 + 100·7 + 1000·5 = 5732 (note that no hussar takes his own horse in this assignment).

After second query we get back to initial situation and optimal assignment is 1·2 + 10·3 + 100·5 + 1000·7 = 7532.

Clarification for the second sample. After first query:

Warriors:  7 11 5Horses:    2  3 1

Optimal assignment is 7·1 + 11·2 + 5·3 = 44.

Then after second query 7·3 + 11·2 + 5·1 = 48.

Finally 7·2 + 11·3 + 5·1 = 52.

Now solve the problem and return the code.