시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 19 10 10 71.429%

문제

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

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

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

입력

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

출력

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

예제 입력 1

4 3
1 3 4 2
1 4 2

예제 출력 1

10 21
W3sicHJvYmxlbV9pZCI6IjIzODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMTRcdWI4NWQgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MDFcdWMyMThcdWIyOTQgXHVhYzAwXHViODVjIE4sIFx1YzEzOFx1Yjg1YyBNIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQzMTAgXHVjNzA0XHVjNWQwLCBcdWFjMDEgXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMzEzXHViMjk0IFx1YjE4MFx1Yzc3NFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIyZTRcdWFjMDAgXHVjOTExXHVhYzA0XHVjNWQwIFx1YzdhMFx1YzJkYyBcdWM5MTFcdWM5YzBcdWQ1NjAgXHVjNzdjXHVjNzc0IFx1YzBkZFx1YWNiY1x1YjI5NFx1YjM3MCwgXHViMDk4XHVjOTExXHVjNWQwIFx1YWNjNFx1YzE4ZCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMzEzXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMzMTNcdWM1NDRcdWIxOTNcdWM3NDAgXHViZTE0XHViODVkXHViNGU0XHVjNzQ0IFx1YzU1ZVx1YmE3NFx1YWNmYyBcdWM2MDZcdWJhNzRcdWM1ZDBcdWMxMWMgXHViY2Y4IFx1YmFhOFx1YzJiNVx1Yzc0NCBcdWFkZjhcdWI4MjQgXHViNDUwXHVjNWM4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNjA4XHViOTdjIFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwM1wvQklOMDAwMSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDVweDsgd2lkdGg6MjE4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNjdjXHVjYWJkXHVjNzQwIFx1YzU1ZVx1YzVkMFx1YzExYyBcdWJjZjggXHViYWE4XHVjMmI1XHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgXHVjNjA2XHVjNWQwXHVjMTFjIFx1YmNmOCBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuIFx1YzYwMVx1YzIxOFx1YjI5NCBcdWIwOThcdWM5MTFcdWM1ZDAgXHViZTE0XHViODVkXHVjNzQ0IFx1YzZkMFx1Yjc5OFx1Yzc1OCBcdWJhYThcdWMyYjVcdWM3M2NcdWI4NWMgXHViY2Y1XHVjNmQwXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU4OFx1YjI5NFx1YjM3MCwgXHViY2Y1XHVjNmQwXHVjNzQ0IFx1ZDU1OFx1YjJlNCBcdWJjZjRcdWIyYzggXHVjNjA4XHVjODA0XHVjNWQwIFx1YWRmOFx1YjgyNFx1YjQ1NCBcdWFkZjhcdWI5YmNcdWI5Y2NcdWM3M2NcdWI4NWNcdWIyOTQgXHVjNmQwXHViNzk4XHVjNzU4IFx1YmFhOFx1YzJiNVx1Yzc3NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVhY2IwXHVjODE1XHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0Y1x1Yzc0NCBcdWM1NGNcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNjAxXHVjMjE4XHViMjk0IFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMjk0XHViMzcwLCBcdWQ1NThcdWIwOThcdWIyOTQgXHViZTE0XHViODVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YWNlMCwgXHViMmU0XHViOTc4IFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTAzXC9CSU4wMDAyKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyOXB4OyB3aWR0aDo0NjZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2N2NcdWNhYmRcdWM3NDAgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0NCBcdWJjMTRcdWQwZDVcdWM3M2NcdWI4NWMgXHViZTE0XHViODVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YzMxM1x1Yzc0MCBcdWFjYmRcdWM2YjBcdWFjZTAsIFx1YWMwMFx1YzZiNFx1YjM3MFx1YjI5NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YzMxM1x1Yzc0MCBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQyMCBcdWI1NGNcdWM3NTggXHViYWE4XHVjMmI1XHVjNzQ0IFx1YjRhNFx1YzVkMFx1YzExYyBcdWJjZjggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWNkNWNcdWIzMDBcdWIyOTQgMjFcdWFjMWNcdWM3NTggXHViZTE0XHViODVkXHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YWNlMCwgXHVjZDVjXHVjMThjXHViMjk0IDEwXHVhYzFjXHVjNzU4IFx1YmUxNFx1Yjg1ZFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTiwgTSgxJmxlO04sIE0mbGU7MTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjLCBcdWMzMTNcdWM1NDQgXHViMTkzXHVjNzQwIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNTU4XHVjNzQ0IFx1YjU0Y1x1Yzc1OCBcdWJhYThcdWMyYjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWIxOTJcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgTVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgaW50IFx1YmM5NFx1YzcwNChcdWM1N2QgMTBeOSlcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YzE4YyBcdWJlMTRcdWI4NWQsIFx1Y2Q1Y1x1YjMwMCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZjVcdWM3NDAgaW50IFx1YmM5NFx1YzcwNFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWI5Y2NcdWM1N2QgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCbG9jayBUb3duIiwiZGVzY3JpcHRpb24iOiI8cD5DaGlsZHJlbiBsaWtlIHBsYXlpbmcgd2l0aCBibG9ja3MgKGN1YmUgd29vZGVuIGJyaWNrcykuIFRoZXkgdXN1YWxseSBidWlsZCBoaWdoIHRvd2VycywgYnV0IHNtYWxsIEpvaG55IGRyZWFtcyBvZiBkaWZmZXJlbnQgcGxhbnMuIEhlIGlzIGdvaW5nIHRvIGJ1aWxkIGEgYmlnIHRvd24uIEhpcyBkYWRkeSBoYXMgYm91Z2h0IGhpbSBhIHJlY3Rhbmd1bGFyIHRhYmxlOyBpdHMgd2lkdGggaXMgSyBibG9ja3MgYW5kIGl0cyBsZW5ndGggaXMgTCBibG9ja3MgZXhhY3RseS4gSm9obnkgZGVjaWRlZCB0byBwcm9qZWN0IGEgcGxhbiBvZiBzdWNoIGEgdG93biBiZWZvcmUgaGUgc3RhcnRzIGJ1aWxkaW5nIHRoZSB0b3duIGl0c2VsZi4gSGUgaGFzIGRyYXduIGEgc3F1YXJlLXNoYXBlZCBuZXR3b3JrIG9uIHRoZSB0YWJsZSBjb25zaXN0aW5nIG9mIEt4TCBzcXVhcmVzLiBIZSB3YW50cyB0byBwbGFjZSB0aGUgdG93ZXJzIGNvbnNpc3Rpbmcgb2Ygb25lIG9yIG1vcmUgYmxvY2tzIG9uIHNvbWUgb2YgdGhlIHNxdWFyZXMgb2YgdGhlIG5ldHdvcmsgZHJhd247IHRoZSByZW1haW5pbmcgc3F1YXJlcyB3aWxsIGJlIGVtcHR5LiBCZWNhdXNlIG9mIHRoZSB0YWJsZSBiZWluZyBzbyBsYXJnZSwgSm9obnkgaXMgbm90IGdvaW5nIHRvIHBsYW4gZXhhY3RseSBmb3IgZXZlcnkgc3F1YXJlIGhvdyBtYW55IGJsb2NrcyBoZSB3aWxsIHB1dCBvbiBpdC4gSGUgb25seSB3YW50cyB0byBkZWNpZGUgYWJvdXQgZnJvbnQgYW5kIHJpZ2h0IHNpZ2h0IHNoYXBlcyBvZiBoaXMgdG93bi4gSGUgZHJldyB0aGVzZSB0d28gdmlld3MgKHR3by1kaW1lbnNpb25hbCBwcm9qZWN0aW9ucyBvZiB0aGUgcGxhbm5lZCB0b3duKSBvbiBhIHBhcGVyLiBZb3UgY2FuIHNlZSBhbiBleGFtcGxlIG9mIHRoZXNlIGRyYXdpbmdzIGFuZCB0aGUgYWRlcXVhdGUgdG93biBtYWRlIG9mIHdvb2RlbiBicmlja3MgaW4gdGhlIHBpY3R1cmVzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2NrdG93bi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNjVweDsgd2lkdGg6NjYycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Sm9obnkmIzM5O3MgZGFkZHkgaXMgYWZyYWlkIHRoZXkgZG9uJiMzOTt0IGhhdmUgZW5vdWdoIGJsb2NrcyB0byBmaW5pc2ggYnVpbGRpbmcgSm9obnkmIzM5O3MgcGxhbm5lZCB0b3duLiBZb3UgYXJlIGFza2VkIGZvciB3cml0aW5nIGEgcHJvZ3JhbSB0byBjb21wdXRlIHRoZSBtaW5pbWFsIGFuZCBtYXhpbWFsIGFtb3VudCBvZiBibG9ja3Mgd2l0aCB3aGljaCBhIHRvd24gY29ycmVzcG9uZGluZyB0byBKb2hueSYjMzk7cyBwbGFucyBjYW4gYmUgYnVpbHQuIE1vcmVvdmVyIHRoZSBwcm9ncmFtIGNhbiBkZWNpZGUgYWJvdXQgdGhlIHBvc3NpYmlsaXR5IG9mIGJ1aWxkaW5nIGEgdG93biBzYXRpc2Z5aW5nIHRoZSB2aWV3cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGZpbGUgVE9XTi5JTiBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgSywgTCAtLSB0aGUgd2lkdGggYW5kIHRoZSBsZW5ndGggb2YgdGhlIHRhYmxlIChleHByZXNzZWQgYXMgbnVtYmVycyBvZiBicmlja3MpLiBOZWl0aGVyIHRoZSB3aWR0aCBub3IgdGhlIGxlbmd0aCBvZiB0aGUgdGFibGUgaXMgZ3JlYXRlciB0aGFuIDEwMDAwMCBicmlja3MuIFRoZSBmb2xsb3dpbmcgbGluZXMgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbiB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIGZyb250IHZpZXcgb2YgdGhlIHRvd24uIFRoZSBkZXNjcmlwdGlvbiBjb25zaXN0cyBvZiBhIHNlcmllcyBvZiBoZWlnaHRzIG9mIHZpc2libGUgYnVpbGRpbmdzIG9uIGVhY2ggc3F1YXJlIGZyb20gdGhlIGxlZnQgdG8gdGhlIHJpZ2h0ICh0aGUgaGVpZ2h0IGlzIG1lYXN1cmVkIGJ5IHRoZSBudW1iZXIgb2YgdGhlIGJsb2NrcywgdG9vKS4gVGhlcmUgaXMgb25seSBvbmUgbnVtYmVyIG9uIGVhY2ggbGluZSwgaS5lLiB0aGUgbnVtYmVyIG9mIHRoZSBsaW5lcyB3aXRoIHRoZSBmcm9udCB2aWV3IGRlc2NyaXB0aW9uIG9mIHRoZSB0b3duIGVxdWFscyBLIC0tIHRoZSB3aWR0aCBvZiB0aGUgdGFibGUuIFNpbWlsYXJseSB0aGUgbmV4dCBMIGxpbmVzIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnRhaW4gdGhlIHJpZ2h0IHNpZ2h0IHZpZXcgb2YgdGhlIHRvd24uIFRoZSBoZWlnaHRzIG9mIHRoZSB3b29kZW4gYmxvY2sgdG93ZXJzIGFyZSBub3cgc3BlY2lmaWVkIGZyb20gdGhlIGZyb250IGxpbmUgdG8gdGhlIGJhY2sgbGluZS4gWW91IG1heSBzdXBwb3NlIHRoZXJlIGlzIG5vIGJ1aWxkaW5nIGluIHRoZSB0b3duIHdpdGggaGVpZ2h0IGV4Y2VlZGluZyA1MDAwIGJsb2Nrcy4gVGhlIG1heGltYWwgbnVtYmVyIG9mIGJsb2NrcyBuZWVkZWQgZm9yIGJ1aWxkaW5nIHRoZSBlbnRpcmUgdG93biBkb2VzIG5vdCBleGNlZWQgMjAwMDAwMDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgZmlsZSBUT1dOLk9VVCBjb250YWlucyBvbmx5IG9uZSBsaW5lLiBJZiBpdCBpcyBub3QgcG9zc2libGUgdG8gYnVpbGQgYSB0b3duIHdpdGggdGhlIGZyb250IGFuZCByaWdodCBzaWdodCB2aWV3cyBnaXZlbiwgb25seSBhIHRleHQgYE5vIHNvbHV0aW9uLiYjMzk7IGlzIHdyaXR0ZW4gdGhlcmUuIEluIHRoZSBvdGhlciBjYXNlIHR3byBudW1iZXJzIHdpbGwgYmUgd3JpdHRlbiBvbiB0aGUgbGluZSBhbmQgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgZmlyc3Qgb25lIGlzIHRoZSBtaW5pbWFsIGFuZCB0aGUgc2Vjb25kIG9uZSBpcyB0aGUgbWF4aW1hbCBhbW91bnQgb2YgYmxvY2tzIHNtYWxsIEpvaG55IGNhbiB1c2UgdG8gYnVpbGQgaGlzIHRvd24gaW4gYWNjb3JkYW5jZSB3aXRoIGhpcyBwcm9qZWN0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==