시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB55720215338.636%

문제

무한히 넓은 당근 밭 가운데 $x$, $y$ 축으로 수평인 직사각형 마구간이 있다. 그림 B.1 의 왼쪽 그림처럼 마구간의 왼쪽 아래 모서리 기둥에 말이 묶여 있고, 마구간의 네 모서리는 모두 격자점에 있다. 상하좌우로 인접한 두 격자점 사이의 간격은 $1$이다. 말을 묶은 줄의 길이는 $L$로 유한하다. 그리고 당근 밭의 모든 격자점마다 하나씩 당근이 심어져 있다. 그리고 말을 묶은 줄이 닿을 수 있는 거리 안에 심어진 당근은 말이 모두 먹을 수 있다고 가정한다.

만일 마구간의 크기가 11 × 6이고 묶은 줄의 길이가 9일때, 말이 먹을 수 있는 당근이 그림 B.1 의 오른쪽 그림에서 점으로 표시되어 있다. 단, 말과 말을 묶은 줄은 마굿간안으로는 들어갈 수 없으며 마굿간의 경계와 내부에는 당근이 심어져 있지 않다.

그림 B.1 (왼쪽) 마구간과 길이 9 인 줄에 묶인 말. (오른쪽) 말이 먹을 수 있는 모든 당근 (점).

마구간의 크기 $w \times h$ 와 말을 묶은 줄의 길이 $L$, 이렇게 3 개의 정수 $w$, $h$, $L$ 이 주어졌을 때, 말이 먹을 수 있는 당근의 최대 개수를 구하는 프로그램을 작성하시오. 격자점과 말을 묶은 기둥과의 거리가 정확하게 $L$인 경우, 이 격자점의 당근은 말이 먹을 수 있음에 유의하자.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 마구간의 크기와 줄의 길이를 나타내는 3 개의 양의 정수 $w$, $h$, $L$ ($1 \le w, h, L \le 100,000$)가 주어진다.

출력

출력은 표준출력을 사용한다. 주어진 조건에서 말이 먹을 수 있는 당근의 최대 개수를 첫 번째 줄에 정수로 출력한다.

예제 입력 1

11 6 3

예제 출력 1

18

그림 B.2 첫 번째 테스트 케이스에 대한 설명

예제 입력 2

11 6 15

예제 출력 2

591

예제 입력 3

11 6 20

예제 출력 3

1134
W3sicHJvYmxlbV9pZCI6IjIzMjM5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmY5XHVhZGZjIFx1YmMyZCIsImRlc2NyaXB0aW9uIjoiPHA+XHViYjM0XHVkNTVjXHVkNzg4IFx1YjExM1x1Yzc0MCBcdWIyZjlcdWFkZmMgXHViYzJkIFx1YWMwMFx1YzZiNFx1YjM3MCAkeCQsICR5JCBcdWNkOTVcdWM3M2NcdWI4NWMgXHVjMjE4XHVkM2M5XHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWI5YzhcdWFkNmNcdWFjMDRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YmMgQi4xIFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjYzk4XHViN2ZjIFx1YjljOFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNTQ0XHViNzk4IFx1YmFhOFx1YzExY1x1YjlhYyBcdWFlMzBcdWI0NjVcdWM1ZDAgXHViOWQwXHVjNzc0IFx1YmIzNlx1YzVlYyBcdWM3ODhcdWFjZTAsIFx1YjljOFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWIxMjQgXHViYWE4XHVjMTFjXHViOWFjXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFjYTlcdWM3OTBcdWM4MTBcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWQ1NThcdWM4OGNcdWM2YjBcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWFjYTlcdWM3OTBcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWMwNFx1YWNhOVx1Yzc0MCAkMSRcdWM3NzRcdWIyZTQuIFx1YjlkMFx1Yzc0NCBcdWJiMzZcdWM3NDAgXHVjOTA0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAkTCRcdWI4NWMgXHVjNzIwXHVkNTVjXHVkNTU4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViMmY5XHVhZGZjIFx1YmMyZFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVhY2E5XHVjNzkwXHVjODEwXHViOWM4XHViMmU0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWIyZjlcdWFkZmNcdWM3NzQgXHVjMmVjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjlkMFx1Yzc0NCBcdWJiMzZcdWM3NDAgXHVjOTA0XHVjNzc0IFx1YjJmZlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhYyBcdWM1NDhcdWM1ZDAgXHVjMmVjXHVjNWI0XHVjOWM0IFx1YjJmOVx1YWRmY1x1Yzc0MCBcdWI5ZDBcdWM3NzQgXHViYWE4XHViNDUwIFx1YmEzOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNzdjIFx1YjljOFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgMTEgJnRpbWVzOyZuYnNwOzZcdWM3NzRcdWFjZTAgXHViYjM2XHVjNzQwIFx1YzkwNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgOVx1Yzc3Y1x1YjU0YywgXHViOWQwXHVjNzc0IFx1YmEzOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjJmOVx1YWRmY1x1Yzc3NCBcdWFkZjhcdWI5YmMgQi4xIFx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YzgxMFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWIyZTgsIFx1YjlkMFx1YWNmYyBcdWI5ZDBcdWM3NDQgXHViYjM2XHVjNzQwIFx1YzkwNFx1Yzc0MCBcdWI5YzhcdWFkN2ZcdWFjMDRcdWM1NDhcdWM3M2NcdWI4NWNcdWIyOTQgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJhNzAgXHViOWM4XHVhZDdmXHVhYzA0XHVjNzU4IFx1YWNiZFx1YWNjNFx1YzY0MCBcdWIwYjRcdWJkODBcdWM1ZDBcdWIyOTQgXHViMmY5XHVhZGZjXHVjNzc0IFx1YzJlY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzYxNWU4NTFiLTU2NTgtNGRlNy04NzhhLWQwNTBlMDZjYzliY1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTQ5cHg7IGhlaWdodDogMjQwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlx1YWRmOFx1YjliYyBCLjEgKFx1YzY3Y1x1Y2FiZCkgXHViOWM4XHVhZDZjXHVhYzA0XHVhY2ZjIFx1YWUzOFx1Yzc3NCA5IFx1Yzc3OCBcdWM5MDRcdWM1ZDAgXHViYjM2XHVjNzc4IFx1YjlkMC4gKFx1YzYyNFx1Yjk3OFx1Y2FiZCkgXHViOWQwXHVjNzc0IFx1YmEzOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIyZjlcdWFkZmMgKFx1YzgxMCkuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWQwNmNcdWFlMzAgJHcmbmJzcDtcXHRpbWVzIGgkIFx1YzY0MCBcdWI5ZDBcdWM3NDQgXHViYjM2XHVjNzQwIFx1YzkwNFx1Yzc1OCBcdWFlMzhcdWM3NzQgJEwkLCBcdWM3NzRcdWI4MDdcdWFjOGMgMyBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICR3JCwgJGgkLCAkTCQgXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjlkMFx1Yzc3NCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZjlcdWFkZmNcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVhY2E5XHVjNzkwXHVjODEwXHVhY2ZjIFx1YjlkMFx1Yzc0NCBcdWJiMzZcdWM3NDAgXHVhZTMwXHViNDY1XHVhY2ZjXHVjNzU4IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgJEwkXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVjNzc0IFx1YWNhOVx1Yzc5MFx1YzgxMFx1Yzc1OCBcdWIyZjlcdWFkZmNcdWM3NDAgXHViOWQwXHVjNzc0IFx1YmEzOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNWQwIFx1YzcyMFx1Yzc1OFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5YzhcdWFkNmNcdWFjMDRcdWM3NTggXHVkMDZjXHVhZTMwXHVjNjQwIFx1YzkwNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IDMgXHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJHckLCAkaCQsICRMJCAoJDEgXFxsZSB3LCBoLCBMIFxcbGUgMTAwLDAwMCQpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwXHVjZDljXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzg3MFx1YWM3NFx1YzVkMFx1YzExYyBcdWI5ZDBcdWM3NzQgXHViYTM5XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmY5XHVhZGZjXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9lM2UxNzdkNS1iODA1LTRiZGEtODA4ZS1kOTlkYjU0MmJiNDRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMxOHB4OyBoZWlnaHQ6IDI0MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cdWFkZjhcdWI5YmMgQi4yIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjMTI0XHViYTg1PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjMyMzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDYXJyb3QgRmllbGQiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBtaWRkbGUgb2YgYW4gaW5maW5pdGVseSB3aWRlIGNhcnJvdCBmaWVsZCwgdGhlcmUgaXMgYSByZWN0YW5ndWxhciBzdGFibGUgd2hvc2Ugc2lkZXMgYXJlIHBhcmFsbGVsIGVpdGhlciB0byAkeCQtYXhpcyBvciB0byAkeSQtYXhpcy4gRWFjaCBjb3JuZXIgb2YgdGhlIHN0YWJsZSBoYXMgaW50ZWdlciBjb29yZGluYXRlcy4gQSBob3JzZSBpcyB0aWVkIHRvIGEgcG9sZSBpbiB0aGUgbG93ZXIgbGVmdCBjb3JuZXIgb2YgdGhlIHN0YWJsZSBhcyBzaG93biBpbiBGaWd1cmUgQi4xLiBUaGUgbGVuZ3RoIG9mIHRoZSBsZWFzaCB0aWVkIHRvIHRoaXMgaG9yc2UgaXMgJEwkLiBBIGNhcnJvdCBpcyBwbGFudGVkIGZvciBldmVyeSB0d28tZGltZW5zaW9uYWwgZ3JpZCBwb2ludCBpbiB0aGUgY2Fycm90IGZpZWxkLCBhbmQgdGhlIGhvcnNlIGNhbiBlYXQgYW55IGNhcnJvdCBwbGFudGVkIHdpdGhpbiB0aGUgcmVhY2ggb2YgdGhlIGxlYXNoLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgdGhlIHNpemUgb2YgdGhlIHN0YWJsZSBpcyAxMSAmdGltZXM7IDYgYW5kIHRoZSBsZW5ndGggb2YgdGhlIGxlYXNoIGlzIDksIHRoZSBjYXJyb3RzIHRoYXQgdGhlIGhvcnNlIGNhbiBlYXQgYXJlIGluZGljYXRlZCBieSB0aGUgZG90cyBpbiB0aGUgcmlnaHQgb2YgRmlndXJlIEIuMSBiZWxvdy4gQnV0IG5vdGUgdGhhdCB0aGUgaG9yc2UgYW5kIHRoZSBsZWFzaCBjYW5ub3QgZW50ZXIgdGhlIHN0YWJsZSwgYW5kIHRoZXJlIGFyZSBubyBjYXJyb3RzIHBsYW50ZWQgb24gdGhlIHNpZGVzIGFuZCB0aGUgaW50ZXJpb3Igb2YgdGhlIHN0YWJsZS48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC82MTVlODUxYi01NjU4LTRkZTctODc4YS1kMDUwZTA2Y2M5YmNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU0OXB4OyBoZWlnaHQ6IDI0MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgQi4xIFRoZSBob3JzZSBpcyB0aWVkIHRvIHRoZSBsb3dlciBsZWZ0IGNvcm5lciBvZiB0aGUgc3RhYmxlIGJ5IHRoZSBsZWFzaCBvZiBsZW5ndGggOSAobGVmdCkuIERvdHMgcmVwcmVzZW50IHRoZSBjYXJyb3RzIHRoYXQgdGhlIGhvcnNlIGNhbiBlYXQgKHJpZ2h0KS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0aHJlZSBpbnRlZ2VycyAkdyQsICRoJCwgYW5kICRMJCB3aGVyZSB0aGUgc3RhYmxlIGhhcyB3aWR0aCAkdyQgYW5kIGhlaWdodCAkaCQsIGFuZCB0aGUgbGVhc2ggaGFzIGxlbmd0aCAkTCQuIFdyaXRlIGEgcHJvZ3JhbSB0byBjb21wdXRlIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjYXJyb3RzIGEgaG9yc2UgY2FuIGVhdC4gTm90ZSB0aGF0IGlmIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIGEgZ3JpZCBwb2ludCBhbmQgdGhlIGNvcm5lciB0byB3aGljaCB0aGUgaG9yc2UgaXMgdGllZCBpcyBleGFjdGx5ICRMJCwgdGhlIGhvcnNlIGNhbiBlYXQgdGhlIGNhcnJvdCBhdCB0aGUgZ3JpZCBwb2ludC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRocmVlIHBvc2l0aXZlIGludGVnZXJzICR3JCwgJGgkLCBhbmQgJEwkICgkMSBcXGxlIHcsIGgsIEwgXFxsZSAxMDAsMDAwJCkgd2hlcmUgJHckIGFuZCAkaCQgcmVwcmVzZW50IHRoZSB3aWR0aCBhbmQgdGhlIGhlaWdodCBvZiB0aGUgc3RhYmxlLCByZXNwZWN0aXZlbHksIGFuZCAkTCQgaXMgdGhlIGxlbmd0aCBvZiB0aGUgbGVhc2guPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSB3aGljaCBjb250YWlucyB0aGUgbWF4aW11bSBudW1iZXIgb2YgY2Fycm90cyBhIGhvcnNlIGNhbiBlYXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2UzZTE3N2Q1LWI4MDUtNGJkYS04MDhlLWQ5OWRiNTQyYmI0NFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzE4cHg7IGhlaWdodDogMjQwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPkZpZ3VyZSBCLjIgVGhlIGlsbHVzdHJhdGlvbiBmb3IgdGhlIGZpcnN0IHNhbXBsZSB0ZXN0IGNhc2UuPFwvcD5cclxuIn1d