시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 173 | 62 | 52 | 44.828% |
영수는 가로 N, 세로 M 크기의 판 위에, 각 변의 길이가 1인 정육면체 블록을 쌓는 놀이를 하고 있었다. 그러다가 중간에 잠시 중지할 일이 생겼는데, 나중에 계속 블록을 쌓기 위해 쌓아놓은 블록들을 앞면과 옆면에서 본 모습을 그려 두었다. 예를 들어 다음과 같은 예를 보자.
왼쪽은 앞에서 본 모습이고, 오른쪽은 옆에서 본 모습이다. 영수는 나중에 블록을 원래의 모습으로 복원하려고 했는데, 복원을 하다 보니 예전에 그려둔 그림만으로는 원래의 모습이 유일하게 결정되지 않음을 알게 되었다. 그래서 영수는 두 가지 경우를 생각해 보기로 했는데, 하나는 블록의 개수가 최대가 되는 경우이고, 다른 하나는 블록의 개수가 최소가 되는 경우이다.
왼쪽은 위의 그림을 바탕으로 블록의 개수가 최대가 되도록 쌓은 경우고, 가운데는 최소가 되도록 쌓은 모습이다. 오른쪽 그림은 최소가 될 때의 모습을 뒤에서 본 것이다. 최대는 21개의 블록이 필요하고, 최소는 10개의 블록이 필요하다.
첫째 줄에 두 정수 N, M(1 ≤ N, M ≤ 100,000)이 주어진다. 다음에는 N개의 정수로, 쌓아 놓은 블록을 앞에서 보았을 때의 모습이 한 줄에 하나씩 주어진다. 이는 왼쪽부터 차례로 높이를 나타낸다. 같은 방식으로 M개의 정수로 각각의 높이가 한 줄에 하나씩 주어진다. 각각의 높이는 231-1을 넘지 않는 음이 아닌 정수다.
첫째 줄에 최소 블록, 최대 블록을 출력한다. 답은 231-1을 넘지 않으며, 만약 불가능한 경우가 주어지면 -1을 출력한다.
4 3 1 3 4 2 1 4 2
10 21