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

문제

상근이는 다음 학기에 먹을 술 값을 벌기 위해서 방학동안 일을 하고 있다. 상근이가 하는 일은 N×N크기의 행렬로 나타낼 수 있으며, 행렬의 각 칸은 작업 하나를 나타낸다. (x, y)에 있는 작업을 하려면, (x, y-1)과 (x-1, y)에 있는 작업을 모두 끝내야 할 수 있다. (그 칸이 존재하는 경우)

위의 그림은 회색 칸에 해당하는 작업을 하기 위해서 먼저 해야하는 작업을 나타낸 것이다.

상근이는 위에서 설명한 일을 수행할 수 있는 컴퓨터 K개를 가지고 있다. 한 컴퓨터는 한 번에 한 작업을 수행할 수 있으며, 일을 끝내는데 1초가 걸린다. 또, 모든 컴퓨터를 동시에 사용하지 않아도 된다. 상근이가 일을 모두 끝내는데 필요한 최소 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 109)

출력

첫째 줄에 일을 끝내는데 필요한 시간의 최솟값을 출력한다.

예제 입력 1

3 2

예제 출력 1

6

예제 입력 2

5 1

예제 출력 2

25

예제 입력 3

4 4

예제 출력 3

7
W3sicHJvYmxlbV9pZCI6IjMwODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3N2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVkNTU5XHVhZTMwXHVjNWQwIFx1YmEzOVx1Yzc0NCBcdWMyMjAgXHVhYzEyXHVjNzQ0IFx1YmM4Y1x1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViYzI5XHVkNTU5XHViM2Q5XHVjNTQ4IFx1Yzc3Y1x1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc0MCBOJnRpbWVzO05cdWQwNmNcdWFlMzBcdWM3NTggXHVkNTg5XHViODJjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWM3OTFcdWM1YzUgXHVkNTU4XHViMDk4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gKHgsIHkpXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0LCAoeCwgeS0xKVx1YWNmYyAoeC0xLCB5KVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWIwNWRcdWIwYjRcdWM1N2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWFkZjggXHVjZTc4XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjApPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMTBhZjBhMDMtYWIyNy00ZGJmLWFjZDMtY2E5YzBlODAwNzc4XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxMTJweDsgaGVpZ2h0OiAxMTNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWQ2OGNcdWMwYzkgXHVjZTc4XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWJhM2NcdWM4MDAgXHVkNTc0XHVjNTdjXHVkNTU4XHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWM3N2NcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwIEtcdWFjMWNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkNTVjIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1ZDU1YyBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yzc3Y1x1Yzc0NCBcdWIwNWRcdWIwYjRcdWIyOTRcdWIzNzAgMVx1Y2QwOFx1YWMwMCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1YjYxMCwgXHViYWE4XHViNGUwIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjMGFjXHVjNmE5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWI0MWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3N2NcdWM3NDQgXHViYWE4XHViNDUwIFx1YjA1ZFx1YjBiNFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOLCBLICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzdjXHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA4NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBPU0FPIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgRG9tYWdvaiBoYXMgaGlzIGhhbmRzIGZ1bGwgb2Ygd29yay4gSGlzIGpvYnMgYXJlIG9yZ2FuaXplZCBpbiBOeE4gbWF0cml4IGluIHN1Y2ggYSB3YXkgdGhhdCBlYWNoIGNlbGwgcmVwcmVzZW50cyBvbmUgam9iLiBIZSBjYW4gc3RhcnQgZG9pbmcgam9iIGF0IGNlbGwgKHgsIHkpIGlmIGFuZCBvbmx5IGlmIGpvYnMgYXQgY2VsbHMgKHgsIHktMSkgYW5kICh4LTEsIHkpIGFyZSBkb25lIChpZiB0aGV5IGV4aXN0KS4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8xMGFmMGEwMy1hYjI3LTRkYmYtYWNkMy1jYTljMGU4MDA3NzhcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDExMnB4OyBoZWlnaHQ6IDExM3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5PbiB0aGUgcGljdHVyZSB0aGUgcmVxdWlyZWQgam9icyBhcmUgc2hvd24gZm9yIGdyYXkgY2VsbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkRvbWFnb2ogaGFzIEsgY29tcHV0ZXJzIHdoaWNoIGhlIHdpbGwgdXNlIGZvciBkb2luZyBqb2JzLiBPbmUgY29tcHV0ZXIgaXMgYWJsZSB0byBkbyBhdCBtb3N0IG9uZSBqb2IgaW4gb25lIHNlY29uZC4gQWxzbywgYWxsIGNvbXB1dGVycyBuZWVkIG5vdCBiZSB1c2VkIGFsbCB0aGUgdGltZS4gSGVscCBEb21hZ29qIGFuZCBvcmdhbml6ZSBvcmRlciBpbiB3aGljaCBjb21wdXRlcnMgd2lsbCBkbyBqb2JzIGluIGxlYXN0IHBvc3NpYmxlIHRpbWUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSB0aGVyZSBhcmUgdHdvIGludGVnZXJzIE4gYW5kIEsgKDEgJmxlOyBOLCBLICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgZGltZW5zaW9ucyBvZiBtYXRyaXggYW5kIG51bWJlciBvZiBjb21wdXRlcnMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgbGVhc3QgcG9zc2libGUgdGltZSBpbiB3aGljaCBhbGwgam9icyBjYW4gYmUgZG9uZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==