시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 34 14 14 53.846%

문제

영수는 가로 N, 세로 M 크기의 판 위에, 각 변의 길이가 1인 정육면체 블록을 쌓는 놀이를 하고 있었다. 그러다가 중간에 잠시 중지할 일이 생겼는데, 나중에 계속 블록을 쌓기 위해 쌓아놓은 블록들을 앞면과 옆면에서 본 모습을 그려 두었다. 예를 들어 다음과 같은 예를 보자.

왼쪽은 앞에서 본 모습이고, 오른쪽은 옆에서 본 모습이다. 영수는 나중에 블록을 원래의 모습으로 복원하려고 했는데, 복원을 하다 보니 예전에 그려둔 그림만으로는 원래의 모습이 유일하게 결정되지 않음을 알게 되었다. 그래서 영수는 두 가지 경우를 생각해 보기로 했는데, 하나는 블록의 개수가 최대가 되는 경우이고, 다른 하나는 블록의 개수가 최소가 되는 경우이다.

왼쪽은 위의 그림을 바탕으로 블록의 개수가 최대가 되도록 쌓은 경우고, 가운데는 최소가 되도록 쌓은 모습이다. 오른쪽 그림은 최소가 될 때의 모습을 뒤에서 본 것이다. 최대는 21개의 블록이 필요하고, 최소는 10개의 블록이 필요하다.

입력

첫째 줄에 두 정수 N, M(1 ≤ N, M ≤ 100,000)이 주어진다. 다음에는 N개의 정수로, 쌓아 놓은 블록을 앞에서 보았을 때의 모습이 한 줄에 하나씩 주어진다. 이는 왼쪽부터 차례로 높이를 나타낸다. 같은 방식으로 M개의 정수로 각각의 높이가 한 줄에 하나씩 주어진다. 각각의 높이는 231-1을 넘지 않는다.

출력

첫째 줄에 최소 블록, 최대 블록을 출력한다. 답은 231-1을 넘지 않으며, 만약 불가능한 경우가 주어지면 -1을 출력한다.

예제 입력 1

4 3
1
3
4
2
1
4
2

예제 출력 1

10 21
W3sicHJvYmxlbV9pZCI6IjIzODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMTRcdWI4NWQgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MDFcdWMyMThcdWIyOTQgXHVhYzAwXHViODVjIE4sIFx1YzEzOFx1Yjg1YyBNIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQzMTAgXHVjNzA0XHVjNWQwLCBcdWFjMDEgXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMzEzXHViMjk0IFx1YjE4MFx1Yzc3NFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIyZTRcdWFjMDAgXHVjOTExXHVhYzA0XHVjNWQwIFx1YzdhMFx1YzJkYyBcdWM5MTFcdWM5YzBcdWQ1NjAgXHVjNzdjXHVjNzc0IFx1YzBkZFx1YWNiY1x1YjI5NFx1YjM3MCwgXHViMDk4XHVjOTExXHVjNWQwIFx1YWNjNFx1YzE4ZCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMzEzXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMzMTNcdWM1NDRcdWIxOTNcdWM3NDAgXHViZTE0XHViODVkXHViNGU0XHVjNzQ0IFx1YzU1ZVx1YmE3NFx1YWNmYyBcdWM2MDZcdWJhNzRcdWM1ZDBcdWMxMWMgXHViY2Y4IFx1YmFhOFx1YzJiNVx1Yzc0NCBcdWFkZjhcdWI4MjQgXHViNDUwXHVjNWM4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNjA4XHViOTdjIFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwM1wvQklOMDAwMSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDVweDsgd2lkdGg6MjE4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNjdjXHVjYWJkXHVjNzQwIFx1YzU1ZVx1YzVkMFx1YzExYyBcdWJjZjggXHViYWE4XHVjMmI1XHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgXHVjNjA2XHVjNWQwXHVjMTFjIFx1YmNmOCBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuIFx1YzYwMVx1YzIxOFx1YjI5NCBcdWIwOThcdWM5MTFcdWM1ZDAgXHViZTE0XHViODVkXHVjNzQ0IFx1YzZkMFx1Yjc5OFx1Yzc1OCBcdWJhYThcdWMyYjVcdWM3M2NcdWI4NWMgXHViY2Y1XHVjNmQwXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU4OFx1YjI5NFx1YjM3MCwgXHViY2Y1XHVjNmQwXHVjNzQ0IFx1ZDU1OFx1YjJlNCBcdWJjZjRcdWIyYzggXHVjNjA4XHVjODA0XHVjNWQwIFx1YWRmOFx1YjgyNFx1YjQ1NCBcdWFkZjhcdWI5YmNcdWI5Y2NcdWM3M2NcdWI4NWNcdWIyOTQgXHVjNmQwXHViNzk4XHVjNzU4IFx1YmFhOFx1YzJiNVx1Yzc3NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVhY2IwXHVjODE1XHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0Y1x1Yzc0NCBcdWM1NGNcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNjAxXHVjMjE4XHViMjk0IFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMjk0XHViMzcwLCBcdWQ1NThcdWIwOThcdWIyOTQgXHViZTE0XHViODVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YWNlMCwgXHViMmU0XHViOTc4IFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTAzXC9CSU4wMDAyKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyOXB4OyB3aWR0aDo0NjZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2N2NcdWNhYmRcdWM3NDAgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0NCBcdWJjMTRcdWQwZDVcdWM3M2NcdWI4NWMgXHViZTE0XHViODVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YzMxM1x1Yzc0MCBcdWFjYmRcdWM2YjBcdWFjZTAsIFx1YWMwMFx1YzZiNFx1YjM3MFx1YjI5NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YzMxM1x1Yzc0MCBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQyMCBcdWI1NGNcdWM3NTggXHViYWE4XHVjMmI1XHVjNzQ0IFx1YjRhNFx1YzVkMFx1YzExYyBcdWJjZjggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWNkNWNcdWIzMDBcdWIyOTQgMjFcdWFjMWNcdWM3NTggXHViZTE0XHViODVkXHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YWNlMCwgXHVjZDVjXHVjMThjXHViMjk0IDEwXHVhYzFjXHVjNzU4IFx1YmUxNFx1Yjg1ZFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTiwgTSgxICZsZTsgTiwgTSAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjLCBcdWMzMTNcdWM1NDQgXHViMTkzXHVjNzQwIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNTU4XHVjNzQ0IFx1YjU0Y1x1Yzc1OCBcdWJhYThcdWMyYjVcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWIxOTJcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIE1cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IDI8c3VwPjMxPFwvc3VwPi0xXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkNWNcdWMxOGMgXHViZTE0XHViODVkLCBcdWNkNWNcdWIzMDAgXHViZTE0XHViODVkXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzQwIDI8c3VwPjMxPFwvc3VwPi0xXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YjljY1x1YzU3ZCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjM4OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJsb2NrIFRvd24iLCJkZXNjcmlwdGlvbiI6IjxwPkNoaWxkcmVuIGxpa2UgcGxheWluZyB3aXRoIGJsb2NrcyAoY3ViZSB3b29kZW4gYnJpY2tzKS4gVGhleSB1c3VhbGx5IGJ1aWxkIGhpZ2ggdG93ZXJzLCBidXQgc21hbGwgSm9obnkgZHJlYW1zIG9mIGRpZmZlcmVudCBwbGFucy4gSGUgaXMgZ29pbmcgdG8gYnVpbGQgYSBiaWcgdG93bi4gSGlzIGRhZGR5IGhhcyBib3VnaHQgaGltIGEgcmVjdGFuZ3VsYXIgdGFibGU7IGl0cyB3aWR0aCBpcyBLIGJsb2NrcyBhbmQgaXRzIGxlbmd0aCBpcyBMIGJsb2NrcyBleGFjdGx5LiBKb2hueSBkZWNpZGVkIHRvIHByb2plY3QgYSBwbGFuIG9mIHN1Y2ggYSB0b3duIGJlZm9yZSBoZSBzdGFydHMgYnVpbGRpbmcgdGhlIHRvd24gaXRzZWxmLiBIZSBoYXMgZHJhd24gYSBzcXVhcmUtc2hhcGVkIG5ldHdvcmsgb24gdGhlIHRhYmxlIGNvbnNpc3Rpbmcgb2YgS3hMIHNxdWFyZXMuIEhlIHdhbnRzIHRvIHBsYWNlIHRoZSB0b3dlcnMgY29uc2lzdGluZyBvZiBvbmUgb3IgbW9yZSBibG9ja3Mgb24gc29tZSBvZiB0aGUgc3F1YXJlcyBvZiB0aGUgbmV0d29yayBkcmF3bjsgdGhlIHJlbWFpbmluZyBzcXVhcmVzIHdpbGwgYmUgZW1wdHkuIEJlY2F1c2Ugb2YgdGhlIHRhYmxlIGJlaW5nIHNvIGxhcmdlLCBKb2hueSBpcyBub3QgZ29pbmcgdG8gcGxhbiBleGFjdGx5IGZvciBldmVyeSBzcXVhcmUgaG93IG1hbnkgYmxvY2tzIGhlIHdpbGwgcHV0IG9uIGl0LiBIZSBvbmx5IHdhbnRzIHRvIGRlY2lkZSBhYm91dCBmcm9udCBhbmQgcmlnaHQgc2lnaHQgc2hhcGVzIG9mIGhpcyB0b3duLiBIZSBkcmV3IHRoZXNlIHR3byB2aWV3cyAodHdvLWRpbWVuc2lvbmFsIHByb2plY3Rpb25zIG9mIHRoZSBwbGFubmVkIHRvd24pIG9uIGEgcGFwZXIuIFlvdSBjYW4gc2VlIGFuIGV4YW1wbGUgb2YgdGhlc2UgZHJhd2luZ3MgYW5kIHRoZSBhZGVxdWF0ZSB0b3duIG1hZGUgb2Ygd29vZGVuIGJyaWNrcyBpbiB0aGUgcGljdHVyZXM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmxvY2t0b3duLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2NXB4OyB3aWR0aDo2NjJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Kb2hueSYjMzk7cyBkYWRkeSBpcyBhZnJhaWQgdGhleSBkb24mIzM5O3QgaGF2ZSBlbm91Z2ggYmxvY2tzIHRvIGZpbmlzaCBidWlsZGluZyBKb2hueSYjMzk7cyBwbGFubmVkIHRvd24uIFlvdSBhcmUgYXNrZWQgZm9yIHdyaXRpbmcgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIG1pbmltYWwgYW5kIG1heGltYWwgYW1vdW50IG9mIGJsb2NrcyB3aXRoIHdoaWNoIGEgdG93biBjb3JyZXNwb25kaW5nIHRvIEpvaG55JiMzOTtzIHBsYW5zIGNhbiBiZSBidWlsdC4gTW9yZW92ZXIgdGhlIHByb2dyYW0gY2FuIGRlY2lkZSBhYm91dCB0aGUgcG9zc2liaWxpdHkgb2YgYnVpbGRpbmcgYSB0b3duIHNhdGlzZnlpbmcgdGhlIHZpZXdzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQmbmJzcDtjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgSywgTCAtLSB0aGUgd2lkdGggYW5kIHRoZSBsZW5ndGggb2YgdGhlIHRhYmxlIChleHByZXNzZWQgYXMgbnVtYmVycyBvZiBicmlja3MpLiBOZWl0aGVyIHRoZSB3aWR0aCBub3IgdGhlIGxlbmd0aCBvZiB0aGUgdGFibGUgaXMgZ3JlYXRlciB0aGFuIDEwMDAwMCBicmlja3MuIFRoZSBmb2xsb3dpbmcgbGluZXMgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbiB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIGZyb250IHZpZXcgb2YgdGhlIHRvd24uIFRoZSBkZXNjcmlwdGlvbiBjb25zaXN0cyBvZiBhIHNlcmllcyBvZiBoZWlnaHRzIG9mIHZpc2libGUgYnVpbGRpbmdzIG9uIGVhY2ggc3F1YXJlIGZyb20gdGhlIGxlZnQgdG8gdGhlIHJpZ2h0ICh0aGUgaGVpZ2h0IGlzIG1lYXN1cmVkIGJ5IHRoZSBudW1iZXIgb2YgdGhlIGJsb2NrcywgdG9vKS4gVGhlcmUgaXMgb25seSBvbmUgbnVtYmVyIG9uIGVhY2ggbGluZSwgaS5lLiB0aGUgbnVtYmVyIG9mIHRoZSBsaW5lcyB3aXRoIHRoZSBmcm9udCB2aWV3IGRlc2NyaXB0aW9uIG9mIHRoZSB0b3duIGVxdWFscyBLIC0tIHRoZSB3aWR0aCBvZiB0aGUgdGFibGUuIFNpbWlsYXJseSB0aGUgbmV4dCBMIGxpbmVzIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnRhaW4gdGhlIHJpZ2h0IHNpZ2h0IHZpZXcgb2YgdGhlIHRvd24uIFRoZSBoZWlnaHRzIG9mIHRoZSB3b29kZW4gYmxvY2sgdG93ZXJzIGFyZSBub3cgc3BlY2lmaWVkIGZyb20gdGhlIGZyb250IGxpbmUgdG8gdGhlIGJhY2sgbGluZS4gWW91IG1heSBzdXBwb3NlIHRoZXJlIGlzIG5vIGJ1aWxkaW5nIGluIHRoZSB0b3duIHdpdGggaGVpZ2h0IGV4Y2VlZGluZyA1MDAwIGJsb2Nrcy4gVGhlIG1heGltYWwgbnVtYmVyIG9mIGJsb2NrcyBuZWVkZWQgZm9yIGJ1aWxkaW5nIHRoZSBlbnRpcmUgdG93biBkb2VzIG5vdCBleGNlZWQgMjAwMDAwMDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgY29udGFpbnMgb25seSBvbmUgbGluZS4gSWYgaXQgaXMgbm90IHBvc3NpYmxlIHRvIGJ1aWxkIGEgdG93biB3aXRoIHRoZSBmcm9udCBhbmQgcmlnaHQgc2lnaHQgdmlld3MgZ2l2ZW4sIG9ubHkgYSB0ZXh0IGBObyBzb2x1dGlvbi4mIzM5OyBpcyB3cml0dGVuIHRoZXJlLiBJbiB0aGUgb3RoZXIgY2FzZSB0d28gbnVtYmVycyB3aWxsIGJlIHdyaXR0ZW4gb24gdGhlIGxpbmUgYW5kIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGZpcnN0IG9uZSBpcyB0aGUgbWluaW1hbCBhbmQgdGhlIHNlY29uZCBvbmUgaXMgdGhlIG1heGltYWwgYW1vdW50IG9mIGJsb2NrcyBzbWFsbCBKb2hueSBjYW4gdXNlIHRvIGJ1aWxkIGhpcyB0b3duIGluIGFjY29yZGFuY2Ugd2l0aCBoaXMgcHJvamVjdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Central European Olympiad in Informatics > CEOI 1999 6번

  • 잘못된 데이터를 찾은 사람: exqt