시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB594935920.068%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

3 4

예제 출력 1

4

예제 입력 2

4 4

예제 출력 2

1

예제 입력 3

2 5

예제 출력 3

4
W3sicHJvYmxlbV9pZCI6IjMwODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkMDhcdWNmNWNcdWI5YmYgXHVjNzkwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHViMGEwXHViNGRjXHVjNWQwXHVjMTFjIE5cdWQ1ODkgTVx1YzVmNCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YzBhY1x1Yzc0MFx1ZDQ4OFx1YzczY1x1Yjg1YyBcdWJjMWJcdWM1NThcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWFlMzBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMGI0XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTRcdWIyOTQgXHViZDgwXHViYWE4XHViMmQ4XHVjNzU4IFx1YWMwMFx1Yjk3NFx1Y2U2OFx1Yzc0NCBcdWI5YzhcdWM3NGNcdWMxOGRcdWM1ZDAgXHVjMGM4XHVhZTMwXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjhcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVhY2ZjIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWIwOThcdWIyMDRcdWM1YjQgXHViYTM5XHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViOTdjIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWNjM2VcdWM1NDRcdWJjZjRcdWIyZTRcdWJjZjRcdWJhNzQgXHViZDg0XHViYTg1XHVkNzg4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0XHViMjk0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWNhYmNcdWFjMWNcdWMxMWMgXHViYWE4XHViNDUwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWJjYTBcdWMyYTRcdWQyYjggXHVkNTA0XHViNzljXHViNGRjXHVjNWQwXHVhYzhjXHViOWNjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI0MThcdWIzYzRcdWI4NWQgXHVjODAxXHVjNzQwIFx1YzIxOFx1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViMGE4XHViM2M0XHViODVkIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWNhYmNcdWFjMWNcdWJjZjRcdWM3OTAuIFx1Yzc3NFx1YjU0YywgXHViYzg0XHViOWFjXHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8xODY3Zjg2ZC01ZGM4LTQ4YTctODE3Ni00MmJiN2IzZWZjMGFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMwM3B4OyBoZWlnaHQ6IDk5cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgTlx1Yzc3NCAzXHVjNzc0XHVhY2UwLCBNXHVjNzc0IDRcdWM3NzhcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NzRcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3NDAgXHVjZDFkIDZcdWFjMWNcdWM3NTggXHVjZDA4XHVjZjVjXHViOWJmXHVjNzNjXHViODVjIFx1Y2FiY1x1YWMyMCBcdWFkZjhcdWI5YmNcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgNFx1YWMxY1x1Yjg1YyBcdWNhYmNcdWFjMjAgXHVhZGY4XHViOWJjXHVjNzc0XHViMmU0LiBcdWM2MjRcdWI5NzhcdWM4NzEgXHVhZGY4XHViOWJjXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWNhYmNcdWFjMWNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkMDhcdWNmNWNcdWI5YmZcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2FiY1x1YWMxY1x1YzExYyBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOLCBNICZsZTsgMTAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWNhYmNcdWFjMWNcdWMxMWMgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwODYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJcdTAxMGNPS09MQURBIiwiZGVzY3JpcHRpb24iOiI8cD5NYXJpbiYjMzk7cyBtb3RoZXIgYm91Z2h0IE1hcmluIGEgY2hvY29sYXRlIGJhciB3aXRoIE4gcm93cyBhbmQgTSBjb2x1bW5zLiBNYXJpbiBrbm93cyBoZSBjYW5ub3QgYmUgc2VsZmlzaCwgc28gaGUgZGVjaWRlZCB0byBzcGxpdCB0aGUgY2hvY29sYXRlIHdpdGggaGlzIGZyaWVuZHMuIEhlIHdpbGwgc3BsaXQgdGhlIGNob2NvbGF0ZSBpbiBzdWNoIGEgd2F5IHRoYXQgaGUgbWFrZXMgY3V0cyBiZXR3ZWVuIHJvd3MgYW5kIGNvbHVtbnMgb2YgcmVtYWluaW5nIGJhcnMgKHN0YXJ0aW5nIHdpdGgganVzdCBvbmUgYmFyKS4gSW4gdGhlIGVuZCwgYWxsIHRoZSByZW1haW5pbmcgYmFycyBtdXN0IGJlIHNxdWFyZSBzaGFwZWQsIGkuZS4gaGF2ZSB0aGUgc2FtZSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucy4gSGUgd2FudHMgdG8gc2hhcmUgdGhlIGNob2NvbGF0ZSB3aXRoIG9ubHkgaGlzIGJlc3QgZnJpZW5kcyBzbyBoZSB3aWxsIHNwbGl0IGl0IGluIHN1Y2ggYSB3YXkgdGhhdCB0aGVyZSBpcyBhIG1pbmltYWwgbnVtYmVyIG9mIHJlbWFpbmluZyBzcXVhcmUgc2hhcGVkIGJhcnMgbGVmdC4gT2YgY291cnNlLCBubyBjaG9jb2xhdGUgY2FuIGJlIHdhc3RlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8xODY3Zjg2ZC01ZGM4LTQ4YTctODE3Ni00MmJiN2IzZWZjMGFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMwM3B4OyBoZWlnaHQ6IDk5cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkluIHRoZSBwaWN0dXJlcyBhYm92ZSwgTiBpcyAzIGFuZCBNIGlzIDQuIEZpcnN0IHNwbGl0IGVuZHMgdXAgd2l0aCA2IHNxdWFyZSBiYXJzIGFuZCB0aGUgc2Vjb25kIG9uZSB3aXRoIDQsIHdoaWNoIGFsc28gbWFrZXMgdGhlIG9wdGltYWwgY3V0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZWxwIE1hcmluIHNwbGl0IGhpcyBjaG9jb2xhdGUgYmFyIGludG8gc21hbGxlc3QgbnVtYmVyIG9mIHNxdWFyZSBzaGFwZWQgYmFycy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIHJlYWQgaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE4sIE0gJmxlOyAxMDAwKSwgdGhlIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zIG9mIHRoZSBjaG9jb2xhdGUgYmFyLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIC0gdGhlIG1pbmltYWwgbnVtYmVyIG9mIHJlbWFpbmluZyBzcXVhcmUgc2hhcGVkIGJhcnMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==