시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 293 30 19 12.179%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

3 4

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjMwODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkMDhcdWNmNWNcdWI5YmYgXHVjNzkwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHViMGEwXHViNGRjXHVjNWQwXHVjMTFjIE5cdWQ1ODkgTVx1YzVmNCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YzBhY1x1Yzc0MFx1ZDQ4OFx1YzczY1x1Yjg1YyBcdWJjMWJcdWM1NThcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWFlMzBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMGI0XHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNFx1YjI5NCBcdWJkODBcdWJhYThcdWIyZDhcdWM3NTggXHVhYzAwXHViOTc0XHVjZTY4XHVjNzQ0IFx1YjljOFx1Yzc0Y1x1YzE4ZFx1YzVkMCBcdWMwYzhcdWFlMzBcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWRmOFx1YjI5NCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWFjZmMgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNCBcdWJhMzlcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWI5N2MgXHVjNWY0XHVjMmVjXHVkNzg4IFx1Y2MzZVx1YzU0NFx1YmNmNFx1YjJlNFx1YmNmNFx1YmE3NCBcdWJkODRcdWJhODVcdWQ3ODggXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTRcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1Y2FiY1x1YWMxY1x1YzExYyBcdWJhYThcdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YmNhMFx1YzJhNFx1ZDJiOCBcdWQ1MDRcdWI3OWNcdWI0ZGNcdWM1ZDBcdWFjOGNcdWI5Y2MgXHViMDk4XHViMjA0XHVjNWI0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWIwYThcdWIzYzRcdWI4NWQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1Y2FiY1x1YWMxY1x1YmNmNFx1Yzc5MC4gXHVjNzc0IFx1YjU0YywgXHViYzg0XHViOWFjXHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Nob2NvLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExM3B4OyB3aWR0aDozMjdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQwIE5cdWM3NzQgM1x1Yzc3NFx1YWNlMCwgTVx1Yzc3NCA0XHVjNzc4XHVjZDA4XHVjZjVjXHViOWJmXHVjNzc0XHViMmU0LiBcdWM2N2NcdWNhYmQgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQwIFx1Y2QxZCA2XHVhYzFjXHVjNzU4IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1YzczY1x1Yjg1YyBcdWNhYmNcdWFjMjAgXHVhZGY4XHViOWJjXHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIDRcdWFjMWNcdWI4NWMgXHVjYWJjXHVhYzIwIFx1YWRmOFx1YjliY1x1Yzc3NFx1YjJlNC4gXHVjNjI0XHViOTc4XHVjODcxIFx1YWRmOFx1YjliY1x1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YzIxOFx1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjYWJjXHVhYzFjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDA4XHVjZjVjXHViOWJmXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNhYmNcdWFjMWNcdWMxMWMgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgTSAmbGU7IDEwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjN2FjIFx1YzkwNFx1YzVkMCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NDQgXHVjYWJjXHVhYzFjXHVjMTFjIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDg2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiXHUwMTBjT0tPTEFEQSIsImRlc2NyaXB0aW9uIjoiPHA+TWFyaW4mIzM5O3MgbW90aGVyIGJvdWdodCBNYXJpbiBhIGNob2NvbGF0ZSBiYXIgd2l0aCBOIHJvd3MgYW5kIE0gY29sdW1ucy4gTWFyaW4ga25vd3MgaGUgY2Fubm90IGJlIHNlbGZpc2gsIHNvIGhlIGRlY2lkZWQgdG8gc3BsaXQgdGhlIGNob2NvbGF0ZSB3aXRoIGhpcyBmcmllbmRzLiBIZSB3aWxsIHNwbGl0IHRoZSBjaG9jb2xhdGUgaW4gc3VjaCBhIHdheSB0aGF0IGhlIG1ha2VzIGN1dHMgYmV0d2VlbiByb3dzIGFuZCBjb2x1bW5zIG9mIHJlbWFpbmluZyBiYXJzIChzdGFydGluZyB3aXRoIGp1c3Qgb25lIGJhcikuIEluIHRoZSBlbmQsIGFsbCB0aGUgcmVtYWluaW5nIGJhcnMgbXVzdCBiZSBzcXVhcmUgc2hhcGVkLCBpLmUuIGhhdmUgdGhlIHNhbWUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMuIEhlIHdhbnRzIHRvIHNoYXJlIHRoZSBjaG9jb2xhdGUgd2l0aCBvbmx5IGhpcyBiZXN0IGZyaWVuZHMgc28gaGUgd2lsbCBzcGxpdCBpdCBpbiBzdWNoIGEgd2F5IHRoYXQgdGhlcmUgaXMgYSBtaW5pbWFsIG51bWJlciBvZiByZW1haW5pbmcgc3F1YXJlIHNoYXBlZCBiYXJzIGxlZnQuIE9mIGNvdXJzZSwgbm8gY2hvY29sYXRlIGNhbiBiZSB3YXN0ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hvY28ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTEzcHg7IHdpZHRoOjMyN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkluIHRoZSBwaWN0dXJlcyBhYm92ZSwgTiBpcyAzIGFuZCBNIGlzIDQuIEZpcnN0IHNwbGl0IGVuZHMgdXAgd2l0aCA2IHNxdWFyZSBiYXJzIGFuZCB0aGUgc2Vjb25kIG9uZSB3aXRoIDQsIHdoaWNoIGFsc28gbWFrZXMgdGhlIG9wdGltYWwgY3V0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZWxwIE1hcmluIHNwbGl0IGhpcyBjaG9jb2xhdGUgYmFyIGludG8gc21hbGxlc3QgbnVtYmVyIG9mIHNxdWFyZSBzaGFwZWQgYmFycy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIHJlYWQgaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE4sIE0gJmxlOyAxMDAwKSwgdGhlIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zIG9mIHRoZSBjaG9jb2xhdGUgYmFyLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIC0gdGhlIG1pbmltYWwgbnVtYmVyIG9mIHJlbWFpbmluZyBzcXVhcmUgc2hhcGVkIGJhcnMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d