시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 297 32 20 12.739%

문제

상근이는 상근날드에서 N행 M열 크기의 초콜릿을 사은품으로 받았다. 상근이는 이기적으로 살면 안된다는 부모님의 가르침을 마음속에 새기고 있었다. 따라서, 그는 친구들과 초콜릿을 나누어 먹으려고 한다.

문제를 열심히 찾아보다보면 분명히 상근이가 정사각형을 좋아한다는 문제를 찾을 수 있을 것이다. 따라서, 상근이는 초콜릿을 쪼개서 모두 정사각형 모양으로 만드려고 한다. 상근이는 초콜릿을 베스트 프랜드에게만 나누어 주려고 한다. 되도록 적은 수의 정사각형이 남도록 초콜릿을 쪼개보자. 이때, 버리는 초콜릿이 있으면 안된다.

위의 그림은 N이 3이고, M이 4인초콜릿이다. 왼쪽 초콜릿은 총 6개의 초콜릿으로 쪼갠 그림이고, 오른쪽 그림은 4개로 쪼갠 그림이다. 오른족 그림이 가장 적은 수의 정사각형으로 쪼개는 방법이다.

초콜릿의 크기가 주어졌을 때, 쪼개서 나올 수 있는 정사각형 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 1000)

출력

첫재 줄에 초콜릿을 쪼개서 나올 수 있는 정사각형 개수의 최솟값을 출력한다.

예제 입력 1

3 4

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjMwODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkMDhcdWNmNWNcdWI5YmYgXHVjNzkwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHViMGEwXHViNGRjXHVjNWQwXHVjMTFjIE5cdWQ1ODkgTVx1YzVmNCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YzBhY1x1Yzc0MFx1ZDQ4OFx1YzczY1x1Yjg1YyBcdWJjMWJcdWM1NThcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWFlMzBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMGI0XHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNFx1YjI5NCBcdWJkODBcdWJhYThcdWIyZDhcdWM3NTggXHVhYzAwXHViOTc0XHVjZTY4XHVjNzQ0IFx1YjljOFx1Yzc0Y1x1YzE4ZFx1YzVkMCBcdWMwYzhcdWFlMzBcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWRmOFx1YjI5NCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWFjZmMgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNCBcdWJhMzlcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWI5N2MgXHVjNWY0XHVjMmVjXHVkNzg4IFx1Y2MzZVx1YzU0NFx1YmNmNFx1YjJlNFx1YmNmNFx1YmE3NCBcdWJkODRcdWJhODVcdWQ3ODggXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTRcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1Y2FiY1x1YWMxY1x1YzExYyBcdWJhYThcdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YmNhMFx1YzJhNFx1ZDJiOCBcdWQ1MDRcdWI3OWNcdWI0ZGNcdWM1ZDBcdWFjOGNcdWI5Y2MgXHViMDk4XHViMjA0XHVjNWI0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWIwYThcdWIzYzRcdWI4NWQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1Y2FiY1x1YWMxY1x1YmNmNFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWJjODRcdWI5YWNcdWIyOTQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hvY28ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTEzcHg7IHdpZHRoOjMyN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgTlx1Yzc3NCAzXHVjNzc0XHVhY2UwLCBNXHVjNzc0IDRcdWM3NzhcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NzRcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NDAgXHVjZDFkIDZcdWFjMWNcdWM3NTggXHVjZDA4XHVjZjVjXHViOWJmXHVjNzNjXHViODVjIFx1Y2FiY1x1YWMyMCBcdWFkZjhcdWI5YmNcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgNFx1YWMxY1x1Yjg1YyBcdWNhYmNcdWFjMjAgXHVhZGY4XHViOWJjXHVjNzc0XHViMmU0LiBcdWM2MjRcdWI5NzhcdWM4NzEgXHVhZGY4XHViOWJjXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWNhYmNcdWFjMWNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkMDhcdWNmNWNcdWI5YmZcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2FiY1x1YWMxY1x1YzExYyBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOLCBNICZsZTsgMTAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWNhYmNcdWFjMWNcdWMxMWMgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwODYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJcdTAxMGNPS09MQURBIiwiZGVzY3JpcHRpb24iOiI8cD5NYXJpbiYjMzk7cyBtb3RoZXIgYm91Z2h0IE1hcmluIGEgY2hvY29sYXRlIGJhciB3aXRoIE4gcm93cyBhbmQgTSBjb2x1bW5zLiBNYXJpbiBrbm93cyBoZSBjYW5ub3QgYmUgc2VsZmlzaCwgc28gaGUgZGVjaWRlZCB0byBzcGxpdCB0aGUgY2hvY29sYXRlIHdpdGggaGlzIGZyaWVuZHMuIEhlIHdpbGwgc3BsaXQgdGhlIGNob2NvbGF0ZSBpbiBzdWNoIGEgd2F5IHRoYXQgaGUgbWFrZXMgY3V0cyBiZXR3ZWVuIHJvd3MgYW5kIGNvbHVtbnMgb2YgcmVtYWluaW5nIGJhcnMgKHN0YXJ0aW5nIHdpdGgganVzdCBvbmUgYmFyKS4gSW4gdGhlIGVuZCwgYWxsIHRoZSByZW1haW5pbmcgYmFycyBtdXN0IGJlIHNxdWFyZSBzaGFwZWQsIGkuZS4gaGF2ZSB0aGUgc2FtZSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucy4gSGUgd2FudHMgdG8gc2hhcmUgdGhlIGNob2NvbGF0ZSB3aXRoIG9ubHkgaGlzIGJlc3QgZnJpZW5kcyBzbyBoZSB3aWxsIHNwbGl0IGl0IGluIHN1Y2ggYSB3YXkgdGhhdCB0aGVyZSBpcyBhIG1pbmltYWwgbnVtYmVyIG9mIHJlbWFpbmluZyBzcXVhcmUgc2hhcGVkIGJhcnMgbGVmdC4gT2YgY291cnNlLCBubyBjaG9jb2xhdGUgY2FuIGJlIHdhc3RlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaG9jby5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTNweDsgd2lkdGg6MzI3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHBpY3R1cmVzIGFib3ZlLCBOIGlzIDMgYW5kIE0gaXMgNC4gRmlyc3Qgc3BsaXQgZW5kcyB1cCB3aXRoIDYgc3F1YXJlIGJhcnMgYW5kIHRoZSBzZWNvbmQgb25lIHdpdGggNCwgd2hpY2ggYWxzbyBtYWtlcyB0aGUgb3B0aW1hbCBjdXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbHAgTWFyaW4gc3BsaXQgaGlzIGNob2NvbGF0ZSBiYXIgaW50byBzbWFsbGVzdCBudW1iZXIgb2Ygc3F1YXJlIHNoYXBlZCBiYXJzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgcmVhZCBpbnRlZ2VycyBOIGFuZCBNICgxICZsZTsgTiwgTSAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgb2YgdGhlIGNob2NvbGF0ZSBiYXIuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb3V0cHV0IGEgc2luZ2xlIGludGVnZXIgLSB0aGUgbWluaW1hbCBudW1iZXIgb2YgcmVtYWluaW5nIHNxdWFyZSBzaGFwZWQgYmFycy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=