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

문제

동혁이는 창고에서 매우 재미있어 보이는 보드 게임을 발견했다. 이 게임의 보드는 R*C개의 정사각형 칸으로 이루어져 있다. 제일 위부터 0번부터 R-1까지 번호가 매겨져 있고, 제일 왼쪽부터 0번부터 C-1까지 번호가 매겨져 있다.

이 보드게임의 칸은 색다른 방법으로 색칠되어 있고, 각 칸은 회색 또는 흰색으로 색칠되어 있다.

행의 번호와 열의 번호를 이진수로 나타냈을 때, 적어도 한 위치에서 1이 겹치면 흰색이다. 예를 들어, (4, 5)는 흰색이다. 이러한 경우가 아니면 회색이다. 예를 들어, (2, 5)는 회색이다.

10*10크기의 보드판은 다음과 같이 생겼다.

동혁이는 자신의 말을 위쪽 오른쪽 그림과 같은 순서로 방문하려고 한다. 말은 (0, 0)에서 시작한다. 이 때, 말이 회색 칸을 몇 번 방문하는지 구하려고 한다.

동혁이의 말이 칸을 K번 방문하게 되면, 피곤하기 때문에 더이상 방문하지 않는다.

N, M, K가 주어졌을 때, 회색칸을 몇 번 방문하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. (1 ≤ R,C ≤ 1,000,000)

둘째 줄에는 K가 주어진다. (1 ≤ K ≤ R*C)

출력

첫째 줄에 동혁이의 말이 방문한 회색 칸의 수를 출력한다.

예제 입력 1

10 10
6

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjI5NjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWI0ZGMgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzY1NSBcdWFlNDBcdWIzZDlcdWQ2MDEiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWNjM2RcdWFjZTBcdWM1ZDBcdWMxMWMgXHViOWU0XHVjNmIwIFx1YzdhY1x1YmJmOFx1Yzc4OFx1YzViNCBcdWJjZjRcdWM3NzRcdWIyOTQgXHViY2Y0XHViNGRjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHViY2Y0XHViNGRjXHViMjk0IFIqQ1x1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzgxY1x1Yzc3YyBcdWM3MDRcdWJkODBcdWQxMzAgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBSLTFcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzgxY1x1Yzc3YyBcdWM2N2NcdWNhYmRcdWJkODBcdWQxMzAgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBDLTFcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NCBcdWJjZjRcdWI0ZGNcdWFjOGNcdWM3ODRcdWM3NTggXHVjZTc4XHVjNzQwIFx1YzBjOVx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjMGM5XHVjZTYwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWQ2OGNcdWMwYzkgXHViNjEwXHViMjk0IFx1ZDc3MFx1YzBjOVx1YzczY1x1Yjg1YyBcdWMwYzlcdWNlNjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ1ODlcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YzVmNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1Yzc0NCBcdWI1NGMsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIDFcdWM3NzQgXHVhY2I5XHVjZTU4XHViYTc0IFx1ZDc3MFx1YzBjOVx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgKDQsIDUpXHViMjk0IFx1ZDc3MFx1YzBjOVx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1NDRcdWIyYzhcdWJhNzQgXHVkNjhjXHVjMGM5XHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMiwgNSlcdWIyOTQgXHVkNjhjXHVjMGM5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxMCoxMFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWQzMTBcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFjYmNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYm9hcmRnYW1lLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDYzMXB4OyBoZWlnaHQ6IDI5MnB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YjlkMFx1Yzc0NCBcdWM3MDRcdWNhYmQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMjFjXHVjMTFjXHViODVjIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjlkMFx1Yzc0MCAoMCwgMClcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWI5ZDBcdWM3NzQgXHVkNjhjXHVjMGM5IFx1Y2U3OFx1Yzc0NCBcdWJhODcgXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWM3NTggXHViOWQwXHVjNzc0IFx1Y2U3OFx1Yzc0NCBLXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1ZDUzY1x1YWNlNFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMzU0XHVjNzc0XHVjMGMxIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdE4sIE0sIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNjhjXHVjMGM5XHVjZTc4XHVjNzQ0IFx1YmE4NyBcdWJjODggXHViYzI5XHViYjM4XHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFIsQyAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBLICZsZTsgUipDKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2Q5XHVkNjAxXHVjNzc0XHVjNzU4IFx1YjlkMFx1Yzc3NCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVkNjhjXHVjMGM5IFx1Y2U3OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKRVoiLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgZm91bmQgYSB2ZXJ5IHVudXN1YWwgZ2FtZSBib2FyZCBpbiBoaXMgYXR0aWMuIFN1cnByaXNpbmdseSwgaXQgY29uc2lzdHMgb2YgUiZtaWRkb3Q7QyBzcXVhcmUgY2VsbHMuIFRoZSByb3dzIGFyZSBudW1iZXJlZCAwIHRvIFImbWludXM7MSB0b3AgdG8gYm90dG9tIGFuZCB0aGUgY29sdW1ucyAwIHRvIEMmbWludXM7MSBsZWZ0IHRvIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGF0IG1ha2VzIHRoZSBib2FyZCB1bnVzdWFsIGlzIHRoZSB3YXkgaW4gd2hpY2ggdGhlIGNlbGxzIGFyZSBjb2xvdXJlZC4gRWFjaCBjZWxsIGlzIGVpdGhlciBncmV5IG9yIHdoaXRlOiZuYnNwOzxcL3A+XHJcblxyXG48cD53aGl0ZSwgaWYgdGhlIHJvdyBhbmQgY29sdW1uIG51bWJlcnMgb2YgdGhlIGNlbGwsIHdoZW4gcmVwcmVzZW50ZWQgaW4gYmluYXJ5LCBoYXZlIGF0IGxlYXN0IG9uZSBkaWdpdCAxIGluIHRoZSBzYW1lIHBvc2l0aW9uLiBGb3IgZXhhbXBsZSwgdGhlIGNlbGwgKDQsIDUpIHdvdWxkIGJlIHdoaXRlLiZuYnNwOzxiciBcLz5cclxuZ3JleSwgb3RoZXJ3aXNlLiBGb3IgZXhhbXBsZSwgdGhlIGNlbGwgKDIsIDUpIHdvdWxkIGJlIGdyZXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgaW1hZ2Ugc2hvd3MgYSBib2FyZCBvZiBzaXplIDEwJm1pZGRvdDsxMC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ib2FyZGdhbWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjkycHg7IG9wYWNpdHk6MC45OyB3aWR0aDo2MzFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5MdWthJiMzOTtzIGhlZGdlaG9nIGxpa2VzIHdhbGtpbmcgb24gdGhpcyB1bnVzdWFsIGJvYXJkIGFuZCBkb2VzIGl0IGluIGFuIHVudXN1YWwgd2F5LiBUaGUgaGVkZ2Vob2cgc3RhcnRzIGhpcyB3YWxrIGluIHRoZSBjZWxsICgwLCAwKSBhbmQgY29udGludWVzIGluIHRoZSB6aWctemFnIHBhdHRlcm4gYXMgaW4gdGhlIHNlY29uZCBpbWFnZSBhYm92ZS4gV2hpbGUgdGhlIGhlZGdlaG9nIGlzIHdhbGtpbmcsIEx1a2EgY291bnRzIGhvdyBtYW55IGdyZXkgc3F1YXJlcyBpdCB2aXNpdGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZnRlciB2aXNpdGluZyBLIHNxdWFyZXMsIHRoZSBoZWRnZWhvZyBnZXRzIHRpcmVkIGFuZCBmYWxscyBhc2xlZXAuIEx1a2EgdGhlbiBnb2VzIHRvIGJlZCB0b28sIGhhcHB5IHRoYXQgaGUgd2FzIGFibGUgY291bnQgdGhlIGdyZXkgc3F1YXJlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+S25vd2luZyB0aGUgZGltZW5zaW9ucyBvZiB0aGUgYm9hcmQgYW5kIHRoZSBudW1iZXIgSyBiZWZvcmVoYW5kLCBob3dldmVyLCBpdCBpcyBwb3NzaWJsZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSByZXN1bHQgZmFzdGVyLiBUaGlzIGlzIHlvdXIgdGFzay4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSICgxICZsZTsgUiAmbGU7IDEgMDAwIDAwMCkgYW5kIEMgKDEgJmxlOyBDICZsZTsgMSAwMDAgMDAwKSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIGJvYXJkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgSyAoMSAmbGU7IEsgJmxlOyBSJm1pZGRvdDtDKSwgdGhlIHRvdGFsIG51bWJlciBvZiBzcXVhcmVzIHRoZSBoZWRnZWhvZyB2aXNpdHMuIE5vdGUgdGhhdCB0aGlzIG51bWJlciBtYXkgbm90IGZpdCBpbiBhIDMyLWJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIGdyZXkgY2VsbHMgdGhlIGhlZGdlaG9nIHZpc2l0cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=