D. Мишка и кавалерия
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы бы хотели поучаствовать в конном сражении с мишками? Я — не очень.

Лимак — мишка гризли. Он генерал ужасной армии Мишляндии. Как вы знаете, самая важная часть армии — это, конечно, кавалерия.

Кавалерия Мишляндии состоит из n воинов и n лошадей. У i-го воина сила равна wi, а у i-й лошади сила равна hi. Воин со своей лошадью называется юнитом. Сила юнита равна произведению сил воина и лошади. Общая сила кавалерии равна сумме сил всех n юнитов. Правильное распределение воинов и лошадей делает кавалерию по-настоящему мощной.

Изначально i-му воину принадлежит i-я лошадь. Вам дано q запросов. После каждого запроса два воина меняются друг с другом лошадьми.

Генерал Лимак должен быть готов к любой возможной ситуации. Что, если бы воинам было запрещено скакать на своих лошадях? Поэтому после каждого запроса вам требуется найти максимальную возможную силу кавалерии, если мы рассматриваем только такие сопоставления воинов лошадям, что ни одному воину не достается его собственная лошадь (можно доказать, что для n ≥ 2 всегда есть не менее одного корректного распределения).

Входные данные

В первой строке содержатся два целых числа через пробел, n и q (2 ≤ n ≤ 30 000, 1 ≤ q ≤ 10 000).

Во второй строке содержится n целых чисел через пробел, w1, w2, ..., wn (1 ≤ wi ≤ 106) — силы воинов.

В третьей строке содержится n целых чисел через пробел, h1, h2, ..., hn (1 ≤ hi ≤ 106) — силы лошадей.

Следующие q строк описывают запросы. i-я из них содержит два целых числа через пробел, ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), индексы воинов, которые меняются лошадьми друг с другом.

Выходные данные

Выведите q строк с ответами на запросы. В i-й строке выведите максимальную возможную силу кавалерии после первых 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
Примечание

Разъяснения к первому примеру:

Воины:    1 10 100 1000

Лошади:   3  7  2    5 

После первого запроса ситуация выглядит следующим образом:

Воины:    1 10 100 1000

Лошади:   3  5  2    7 

Мы можем получить 1·2 + 10·3 + 100·7 + 1000·5 = 5732 (обратите внимание, что ни один всадник не сядет на свою собственную лошадь в таком случае).

После второго запроса мы вернемся к изначальной ситуации и оптимальное распределение таково: 1·2 + 10·3 + 100·5 + 1000·7 = 7532.

Разъяснение ко второму примеру. После первого запроса:

Воины:   7 11 5

Кони:    2  3 1

Оптимальное распределение — 7·1 + 11·2 + 5·3 = 44.

После второго запроса — 7·3 + 11·2 + 5·1 = 48.

В конце — 7·2 + 11·3 + 5·1 = 52.