시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Bajtłomieja czeka pierwsza w życiu podróż za ocean, do Stanów Zjednoczonych Bajtocji. Bardzo chce zobaczyć Bajhattan, dzielnicę jednego z tamtejszych ogromnych miast. Na Bajhattanie znajduje się mnóstwo wysokich wieżowców. Znana jest jego panorama, czyli widok na budynki z oddali.

Bajhattan składa się z n × m kwartałów. Każdy kwartał jest albo pusty, albo zajęty przez dokładnie jeden wieżowiec o pewnej wysokości. Dla uproszczenia, puste kwartały utożsamiamy z kwartałami zajętymi przez wieżowce o wysokości 0. Pomijamy również ulice pomiędzy kwartałami. Przykładowo, dla n = 3, m = 4 oraz wysokości wieżowców jak w tabelce (widok z lotu ptaka, północ na górze tabelki)

1 2 0 3
1 0 1 2
2 1 0 1

Bajhattan wygląda jak na rysunku poniżej:

Bajtłomiej widział Bajhattan tylko na zdjęciach. Najbardziej znane są dwie panoramy, zachodnia oraz południowa. W przykładzie, w panoramie zachodniej wybijają się wieżowce o wysokościach 3, 2 oraz 2, a w panoramie południowej wieżowce o wysokościach 2, 2, 1 oraz 3. Zdjęcia były robione z dosyć daleka, więc widoczne są na nich jedynie zarysy budynków.

Dla układu wieżowców z przykładu, panorama zachodnia wygląda następująco:

A oto panorama południowa:

Bajtłomiej chciałby ustalić na podstawie zdjęć, jak duże są wieżowce na Bajhattanie. Chciałby oszacować ich objętość (kubaturę).

Pomóż mu i powiedz, jaka jest maksymalna możliwa kubatura wszystkich wieżowców Bajhattanu. W przykładzie, kubatura wszystkich wieżowców wynosi 14, ale jeśli ich układ byłby nieco inny (ale panoramy wciąż takie same), kubatura mogłaby wynieść aż 22.

입력

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n oraz m (1 ≤ n, m ≤ 1 000 000). Kolejny wiersz zawiera n liczb całkowitych zi (1 ≤ in), określających wysokości kolejnych wieżowców w panoramie zachodniej, począwszy od wieżowca najbardziej wysuniętego na północ. Trzeci wiersz zawiera m liczb całkowitych pj (1 ≤ jm), określających wysokości kolejnych wieżowców w panoramie południowej, począwszy od wieżowca najbardziej wysuniętego na zachód. Możesz założyć, że 0 ≤ zi, pj ≤ 1 000 000.

출력

Twój program powinien wypisać na wyjście maksymalną możliwą kubaturę Bajhattanu. Jeśli Bajtłomiej pomylił się (na przykład biorąc jedną panoramę Bajhattanu i jedną San Bajcisko, które również odwiedza) i zdjęcia nie mogą przedstawiać tego samego miasta, wypisz jedno słowo NIE.

예제 입력 1

3 4
3 2 2
2 2 1 3

예제 출력 1

22

예제 입력 2

3 3
0 0 0
2 2 2

예제 출력 2

NIE