CF457B Distributed Join

Piegirl was asked to implement two table join operation for distributed database system, minimizing the network traffic. Suppose she wants to join two tables, $ A $ and $ B $ . Each of them has certain number of rows which are distributed on different number of partitions. Table $ A $ is distributed on the first cluster consisting of $ m $ partitions. Partition with index $ i $ has $ a_{i} $ rows from $ A $ . Similarly, second cluster containing table $ B $ has $ n $ partitions, $ i $ -th one having $ b_{i} $ rows from $ B $ . In one network operation she can copy one row from any partition to any other partition. At the end, for each row from $ A $ and each row from $ B $ there should be a partition that has both rows. Determine the minimal number of network operations to achieve this.

First line contains two integer numbers, $ m $ and $ n $ ( $ 1

Print one integer — minimal number of copy operations.

In the first example it makes sense to move all the rows to the second partition of the second cluster which is achieved in $ 2+6+3=11 $ operations In the second example Piegirl can copy each row from $ B $ to the both partitions of the first cluster which needs $ 2·3=6 $ copy operations.