码农谷 > 问答 > 编程题 > Bear and Cavalry

Bear and Cavalry

提问者: 老码农     发布时间:2017-01-11     浏览:54     回复:0     悬赏:0.0 谷币

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

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

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


输入样例:
4 2
1 10 100 1000
3 7 2 5
2 4
2 4

输出样例:
5732
7532

我要挑战
其他解答 共0条
 
温馨提示:本问答中心的任何言论仅代表发言者个人的观点,与码农谷立场无关。请对您的言论负责,遵守中华人民共和国有关法律、法规。如果您的言论违反码农谷问答中心的规则,将会被删除。
验证码: 看不清?点击图片更换    

关注码农谷微信
专家推荐
老码农     向TA提问 最佳答案:67
冰点     向TA提问 最佳答案:28
itner     向TA提问 最佳答案:11
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1