시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 10 5 38.462%

문제

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

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

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

입력

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

출력

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

예제 입력 1

3 2

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjMwODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3N2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVkNTU5XHVhZTMwXHVjNWQwIFx1YmEzOVx1Yzc0NCBcdWMyMjAgXHVhYzEyXHVjNzQ0IFx1YmM4Y1x1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViYzI5XHVkNTU5XHViM2Q5XHVjNTQ4IFx1Yzc3Y1x1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc0MCBOJnRpbWVzO05cdWQwNmNcdWFlMzBcdWM3NTggXHVkNTg5XHViODJjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWM3OTFcdWM1YzUgXHVkNTU4XHViMDk4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gKHgsIHkpXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0LCAoeCwgeS0xKVx1YWNmYyAoeC0xLCB5KVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWIwNWRcdWIwYjRcdWM1N2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWFkZjggXHVjZTc4XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjApPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvam9iLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyM3B4OyB3aWR0aDoxMjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQwIFx1ZDY4Y1x1YzBjOSBcdWNlNzhcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmEzY1x1YzgwMCBcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1Yzc3Y1x1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNlZjRcdWQ0ZThcdWQxMzAgS1x1YWMxY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ1NWMgXHVjZWY0XHVkNGU4XHVkMTMwXHViMjk0IFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVkNTVjIFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNzdjXHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YjI5NFx1YjM3MCAxXHVjZDA4XHVhYzAwIFx1YWM3OFx1YjliMFx1YjJlNC4gXHViNjEwLCBcdWJhYThcdWI0ZTAgXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yzc3Y1x1Yzc0NCBcdWJhYThcdWI0NTAgXHViMDVkXHViMGI0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIEsgJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3N2NcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUE9TQU8iLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBEb21hZ29qIGhhcyBoaXMgaGFuZHMgZnVsbCBvZiB3b3JrLiBIaXMgam9icyBhcmUgb3JnYW5pemVkIGluIE54TiBtYXRyaXggaW4gc3VjaCBhIHdheSB0aGF0IGVhY2ggY2VsbCByZXByZXNlbnRzIG9uZSBqb2IuIEhlIGNhbiBzdGFydCBkb2luZyBqb2IgYXQgY2VsbCAoeCwgeSkgaWYgYW5kIG9ubHkgaWYgam9icyBhdCBjZWxscyAoeCwgeS0xKSBhbmQgKHgtMSwgeSkgYXJlIGRvbmUgKGlmIHRoZXkgZXhpc3QpLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvYi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjNweDsgd2lkdGg6MTI0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+T24gdGhlIHBpY3R1cmUgdGhlIHJlcXVpcmVkIGpvYnMgYXJlIHNob3duIGZvciBncmF5IGNlbGxzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Eb21hZ29qIGhhcyBLIGNvbXB1dGVycyB3aGljaCBoZSB3aWxsIHVzZSBmb3IgZG9pbmcgam9icy4gT25lIGNvbXB1dGVyIGlzIGFibGUgdG8gZG8gYXQgbW9zdCBvbmUgam9iIGluIG9uZSBzZWNvbmQuIEFsc28sIGFsbCBjb21wdXRlcnMgbmVlZCBub3QgYmUgdXNlZCBhbGwgdGhlIHRpbWUuIEhlbHAgRG9tYWdvaiBhbmQgb3JnYW5pemUgb3JkZXIgaW4gd2hpY2ggY29tcHV0ZXJzIHdpbGwgZG8gam9icyBpbiBsZWFzdCBwb3NzaWJsZSB0aW1lLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgdGhlcmUgYXJlIHR3byBpbnRlZ2VycyBOIGFuZCBLICgxICZsZTsgTiwgSyAmbGU7IDEwPHN1cD45PFwvc3VwPiksIGRpbWVuc2lvbnMgb2YgbWF0cml4IGFuZCBudW1iZXIgb2YgY29tcHV0ZXJzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IGxlYXN0IHBvc3NpYmxlIHRpbWUgaW4gd2hpY2ggYWxsIGpvYnMgY2FuIGJlIGRvbmUuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==