시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 332 45 25 15.060%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

3 4

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjMwODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkMDhcdWNmNWNcdWI5YmYgXHVjNzkwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHViMGEwXHViNGRjXHVjNWQwXHVjMTFjIE5cdWQ1ODkgTVx1YzVmNCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1YzBhY1x1Yzc0MFx1ZDQ4OFx1YzczY1x1Yjg1YyBcdWJjMWJcdWM1NThcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWFlMzBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMGI0XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTRcdWIyOTQgXHViZDgwXHViYWE4XHViMmQ4XHVjNzU4IFx1YWMwMFx1Yjk3NFx1Y2U2OFx1Yzc0NCBcdWI5YzhcdWM3NGNcdWMxOGRcdWM1ZDAgXHVjMGM4XHVhZTMwXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjhcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVhY2ZjIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWIwOThcdWIyMDRcdWM1YjQgXHViYTM5XHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViOTdjIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWNjM2VcdWM1NDRcdWJjZjRcdWIyZTRcdWJjZjRcdWJhNzQgXHViZDg0XHViYTg1XHVkNzg4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0XHViMjk0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWNhYmNcdWFjMWNcdWMxMWMgXHViYWE4XHViNDUwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWJjYTBcdWMyYTRcdWQyYjggXHVkNTA0XHViNzljXHViNGRjXHVjNWQwXHVhYzhjXHViOWNjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI0MThcdWIzYzRcdWI4NWQgXHVjODAxXHVjNzQwIFx1YzIxOFx1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViMGE4XHViM2M0XHViODVkIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0NCBcdWNhYmNcdWFjMWNcdWJjZjRcdWM3OTAuIFx1Yzc3NFx1YjU0YywgXHViYzg0XHViOWFjXHViMjk0IFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaG9jby5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTNweDsgd2lkdGg6MzI3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBOXHVjNzc0IDNcdWM3NzRcdWFjZTAsIE1cdWM3NzQgNFx1Yzc3OFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc3NFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc0MCBcdWNkMWQgNlx1YWMxY1x1Yzc1OCBcdWNkMDhcdWNmNWNcdWI5YmZcdWM3M2NcdWI4NWMgXHVjYWJjXHVhYzIwIFx1YWRmOFx1YjliY1x1Yzc3NFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCA0XHVhYzFjXHViODVjIFx1Y2FiY1x1YWMyMCBcdWFkZjhcdWI5YmNcdWM3NzRcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Yzg3MSBcdWFkZjhcdWI5YmNcdWM3NzQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1Y2FiY1x1YWMxY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2QwOFx1Y2Y1Y1x1YjliZlx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjYWJjXHVhYzFjXHVjMTFjIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIE0gJmxlOyAxMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzdhYyBcdWM5MDRcdWM1ZDAgXHVjZDA4XHVjZjVjXHViOWJmXHVjNzQ0IFx1Y2FiY1x1YWMxY1x1YzExYyBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzA4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ilx1MDEwY09LT0xBREEiLCJkZXNjcmlwdGlvbiI6IjxwPk1hcmluJiMzOTtzIG1vdGhlciBib3VnaHQgTWFyaW4gYSBjaG9jb2xhdGUgYmFyIHdpdGggTiByb3dzIGFuZCBNIGNvbHVtbnMuIE1hcmluIGtub3dzIGhlIGNhbm5vdCBiZSBzZWxmaXNoLCBzbyBoZSBkZWNpZGVkIHRvIHNwbGl0IHRoZSBjaG9jb2xhdGUgd2l0aCBoaXMgZnJpZW5kcy4gSGUgd2lsbCBzcGxpdCB0aGUgY2hvY29sYXRlIGluIHN1Y2ggYSB3YXkgdGhhdCBoZSBtYWtlcyBjdXRzIGJldHdlZW4gcm93cyBhbmQgY29sdW1ucyBvZiByZW1haW5pbmcgYmFycyAoc3RhcnRpbmcgd2l0aCBqdXN0IG9uZSBiYXIpLiBJbiB0aGUgZW5kLCBhbGwgdGhlIHJlbWFpbmluZyBiYXJzIG11c3QgYmUgc3F1YXJlIHNoYXBlZCwgaS5lLiBoYXZlIHRoZSBzYW1lIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zLiBIZSB3YW50cyB0byBzaGFyZSB0aGUgY2hvY29sYXRlIHdpdGggb25seSBoaXMgYmVzdCBmcmllbmRzIHNvIGhlIHdpbGwgc3BsaXQgaXQgaW4gc3VjaCBhIHdheSB0aGF0IHRoZXJlIGlzIGEgbWluaW1hbCBudW1iZXIgb2YgcmVtYWluaW5nIHNxdWFyZSBzaGFwZWQgYmFycyBsZWZ0LiBPZiBjb3Vyc2UsIG5vIGNob2NvbGF0ZSBjYW4gYmUgd2FzdGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Nob2NvLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExM3B4OyB3aWR0aDozMjdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGUgcGljdHVyZXMgYWJvdmUsIE4gaXMgMyBhbmQgTSBpcyA0LiBGaXJzdCBzcGxpdCBlbmRzIHVwIHdpdGggNiBzcXVhcmUgYmFycyBhbmQgdGhlIHNlY29uZCBvbmUgd2l0aCA0LCB3aGljaCBhbHNvIG1ha2VzIHRoZSBvcHRpbWFsIGN1dC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGVscCBNYXJpbiBzcGxpdCBoaXMgY2hvY29sYXRlIGJhciBpbnRvIHNtYWxsZXN0IG51bWJlciBvZiBzcXVhcmUgc2hhcGVkIGJhcnMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSByZWFkIGludGVnZXJzIE4gYW5kIE0gKDEgJmxlOyBOLCBNICZsZTsgMTAwMCksIHRoZSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucyBvZiB0aGUgY2hvY29sYXRlIGJhci4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciAtIHRoZSBtaW5pbWFsIG51bWJlciBvZiByZW1haW5pbmcgc3F1YXJlIHNoYXBlZCBiYXJzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==