Eating chocolate X32034


Statement
 

pdf   zip

html

Pau has a chocolate bar with n × m (1 ≤ n, m ≤ 105) pieces and he wants to eat it.

In order to do so, Pau decides to apply the following procedure: he selects either a row or a column with at least one remaining piece and then he eats all the pieces that were left.

Each row and each column has a pleasure accumulator associated, indicating the number of pleasure units that Pau will obtain for each piece he eats if he selected that row or column. Considering all of this, compute the maximum amount of pleasure that Pau can achieve.

Input

The input contains several test cases. Each case begins with two integers n and m. A line follows containing n numbers with the pleasure accumulators of the n rows, then another line with m numbers with the pleasure accumulators of the m columns. Every pleasure accumulator is an integer number between 1 and 104.

Output

For each case, print the maximum pleasure that can be achieved.

Public test cases
  • Input

    2 2
    1 2
    1 1
    4 3
    2 5 3 4
    1 5 1
    

    Output

    6
    48
    
  • Input

    2 2
    4 2
    3 1
    1 1
    10
    20

    Output

    13
    20
    
  • Information
    Author
    Félix Moreno
    Language
    English
    Translator
    Alex Alvarez
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python