바이해튼 파노라마

바이트워미에이(Bajtłomiej)는 태어나서 처음으로 바다 건너 바이토시아 합중국으로 여행을 떠난다. 그가 가장 보고 싶어 하는 곳은 그곳의 거대 도시 중 하나에 있는 구역인 바이해튼(Bajhattan)이다. 바이해튼에는 높은 마천루가 아주 많고, 멀리서 건물들을 바라본 모습인 파노라마가 유명하다.

바이해튼은 $n \times m$개의 블록으로 이루어져 있다. 각 블록은 비어 있거나, 어떤 높이를 가진 마천루 하나로 정확히 채워져 있다. 편의상 빈 블록은 높이 $0$짜리 마천루가 있는 블록으로 본다. 블록 사이의 도로는 무시한다. 예를 들어 $n = 3$, $m = 4$이고 마천루 높이가 아래 표(위에서 내려다본 모습, 표의 위쪽이 북쪽)와 같다고 하자.

이때 바이해튼은 아래 그림과 같은 모습이다.

바이트워미에이는 바이해튼을 사진으로만 보았다. 가장 유명한 파노라마는 서쪽 파노라마와 남쪽 파노라마 두 가지다. 위 예시에서 서쪽 파노라마에는 높이 3, 2, 2인 마천루가 두드러지고, 남쪽 파노라마에는 높이 2, 2, 1, 3인 마천루가 두드러진다. 사진은 꽤 멀리서 찍혔기 때문에 건물의 윤곽만 보인다.

다시 말해, 서쪽 파노라마의 $i$번째 값은 (북쪽에서부터 센) $i$번째 행에서 가장 높은 마천루의 높이이고, 남쪽 파노라마의 $j$번째 값은 (서쪽에서부터 센) $j$번째 열에서 가장 높은 마천루의 높이이다.

예시의 배치에서 서쪽 파노라마는 다음과 같다.

그리고 남쪽 파노라마는 다음과 같다.

바이트워미에이는 이 사진들만 보고 바이해튼의 마천루들이 얼마나 큰지 가늠해 보고 싶어 한다. 그는 마천루 전체의 부피(체적)를 어림잡고 싶다.

그를 도와, 바이해튼의 모든 마천루가 가질 수 있는 부피의 최댓값을 구하여라. 예시에서 실제 마천루 전체의 부피는 14이지만, 파노라마는 그대로 두고 배치만 조금 다르게 하면 부피는 최대 22까지 커질 수 있다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 10^6$). 둘째 줄에는 서쪽 파노라마에 나타나는 마천루들의 높이 $z_i$ ($1 \le i \le n$)가 가장 북쪽 마천루부터 차례로 $n$개 주어진다. 셋째 줄에는 남쪽 파노라마에 나타나는 마천루들의 높이 $p_j$ ($1 \le j \le m$)가 가장 서쪽 마천루부터 차례로 $m$개 주어진다. $0 \le z_i, p_j \le 10^6$임이 보장된다.

바이해튼이 가질 수 있는 부피의 최댓값을 한 줄에 출력한다. 만약 바이트워미에이가 착각하여 (예를 들어 바이해튼의 파노라마 한 장과, 그가 함께 방문한 산 바이시스코(San Bajcisko)의 파노라마 한 장을 섞어서) 두 사진이 같은 도시를 나타낼 수 없다면, 대신 NIE라는 한 단어를 출력한다.