Piegirl должна объединить две таблицы (операция join) распределенной базы данных, передавая минимально возможный объем трафика по сети.
Предположим, что имеются две таблицы A и B. Каждая из них состоит из нескольких строк, которые хранятся распределено. Кластер, в котором хранится таблица A, разделен на m частей, причем i-я часть кластера содержит ai строк таблицы A. Кластер, в котором хранится таблица B, разделен на n частей, причем i-я часть кластера содержит bi строк таблицы B.
С помощью одной сетевой команды, Piegirl может скопировать любую одну строку из любой части любого кластера в любую часть любого кластера. В итоге для любой строки из таблицы A и любой строки из таблицы B должна существовать часть какого-то кластера, в которой содержатся обе эти строки. За какое минимальное количество сетевых команд можно этого добиться?
Выходные данные
Выведите целое число — минимальное количество операций.
Примечание
В первом примере оптимальным решением является: скопировать все недостающие строки во вторую часть второго кластера. В итоге, понадобится 2 + 6 + 3 = 11 операций.
Во втором примере оптимальное решение: скопировать все строки таблицы B в первую и вторую части первого кластера. Итого понадобится 2·3 = 6 операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
2 6
3 100
|
11
|
|
2
|
2 3
10 10
1 1 1
|
6
|