Menjant xocolata X15650


Statement
 

pdf   zip

html

En Pau té una rajola de xocolata amb n × m preses i vol menjar-se-la tota. Per fer-ho, repetidament seleccionarà una fila o una columna on quedi com a mínim una presa i es menjarà totes les preses que quedin a la fila o columna en qüestió.

Cada fila i cada columna té un acumulador de plaer, el qual indica les unitats de plaer que s’obtenen per cada presa que es menja si se selecciona aquella fila o columna.

Tenint en compte tot això, calculeu la màxima quantitat de plaer que pot aconseguir en Pau.

Entrada

L’entrada conté diversos casos de prova. Cada cas comença amb els dos enters n i m, ambdós entre 1 i 105. A continuació ve una línia amb n nombres indicant els acumuladors de plaer de les n files, i una altra línia amb m nombres indicant els acumuladors de plaer de les m columnes. Tots els acumuladors són nombres enters entre 1 i 104.

Sortida

Per a cada cas, escriviu el màxim plaer que pot aconseguir en Pau.

Observació

Tingueu en compte que el resultat final és massa gran per guardar en un int de C++. Feu servir long long.

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
    Catalan
    Other languages
    English
    Official solutions
    C++ Python
    User solutions