시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 23 6 6 46.154%

문제

동혁이는 창고에서 매우 재미있어 보이는 보드 게임을 발견했다. 이 게임의 보드는 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+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YjlkMFx1Yzc0NCBcdWM3MDRcdWNhYmQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMjFjXHVjMTFjXHViODVjIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjlkMFx1Yzc0MCAoMCwgMClcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjlkMFx1Yzc3NCBcdWQ2OGNcdWMwYzkgXHVjZTc4XHVjNzQ0IFx1YmE4NyBcdWJjODggXHViYzI5XHViYjM4XHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1Yzc1OCBcdWI5ZDBcdWM3NzQgXHVjZTc4XHVjNzQ0IEtcdWJjODggXHViYzI5XHViYjM4XHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3NCwgXHVkNTNjXHVhY2U0XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIzNTRcdWM3NzRcdWMwYzEgXHViYzI5XHViYjM4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0TiwgTSwgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQ2OGNcdWMwYzlcdWNlNzhcdWM3NDQgXHViYTg3IFx1YmM4OCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUixDICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEsgJmxlOyBSKkMpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWM3NTggXHViOWQwXHVjNzc0IFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWQ2OGNcdWMwYzkgXHVjZTc4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk2OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkpFWiIsImRlc2NyaXB0aW9uIjoiPHA+THVrYSBmb3VuZCBhIHZlcnkgdW51c3VhbCBnYW1lIGJvYXJkIGluIGhpcyBhdHRpYy4gU3VycHJpc2luZ2x5LCBpdCBjb25zaXN0cyBvZiBSJm1pZGRvdDtDIHNxdWFyZSBjZWxscy4gVGhlIHJvd3MgYXJlIG51bWJlcmVkIDAgdG8gUiZtaW51czsxIHRvcCB0byBib3R0b20gYW5kIHRoZSBjb2x1bW5zIDAgdG8gQyZtaW51czsxIGxlZnQgdG8gcmlnaHQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldoYXQgbWFrZXMgdGhlIGJvYXJkIHVudXN1YWwgaXMgdGhlIHdheSBpbiB3aGljaCB0aGUgY2VsbHMgYXJlIGNvbG91cmVkLiBFYWNoIGNlbGwgaXMgZWl0aGVyIGdyZXkgb3Igd2hpdGU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPndoaXRlLCBpZiB0aGUgcm93IGFuZCBjb2x1bW4gbnVtYmVycyBvZiB0aGUgY2VsbCwgd2hlbiByZXByZXNlbnRlZCBpbiBiaW5hcnksIGhhdmUgYXQgbGVhc3Qgb25lIGRpZ2l0IDEgaW4gdGhlIHNhbWUgcG9zaXRpb24uIEZvciBleGFtcGxlLCB0aGUgY2VsbCAoNCwgNSkgd291bGQgYmUgd2hpdGUuJm5ic3A7PGJyIFwvPlxyXG5ncmV5LCBvdGhlcndpc2UuIEZvciBleGFtcGxlLCB0aGUgY2VsbCAoMiwgNSkgd291bGQgYmUgZ3JleS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBpbWFnZSBzaG93cyBhIGJvYXJkIG9mIHNpemUgMTAmbWlkZG90OzEwLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JvYXJkZ2FtZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyOTJweDsgb3BhY2l0eTowLjk7IHdpZHRoOjYzMXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkx1a2EmIzM5O3MgaGVkZ2Vob2cgbGlrZXMgd2Fsa2luZyBvbiB0aGlzIHVudXN1YWwgYm9hcmQgYW5kIGRvZXMgaXQgaW4gYW4gdW51c3VhbCB3YXkuIFRoZSBoZWRnZWhvZyBzdGFydHMgaGlzIHdhbGsgaW4gdGhlIGNlbGwgKDAsIDApIGFuZCBjb250aW51ZXMgaW4gdGhlIHppZy16YWcgcGF0dGVybiBhcyBpbiB0aGUgc2Vjb25kIGltYWdlIGFib3ZlLiBXaGlsZSB0aGUgaGVkZ2Vob2cgaXMgd2Fsa2luZywgTHVrYSBjb3VudHMgaG93IG1hbnkgZ3JleSBzcXVhcmVzIGl0IHZpc2l0ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIHZpc2l0aW5nIEsgc3F1YXJlcywgdGhlIGhlZGdlaG9nIGdldHMgdGlyZWQgYW5kIGZhbGxzIGFzbGVlcC4gTHVrYSB0aGVuIGdvZXMgdG8gYmVkIHRvbywgaGFwcHkgdGhhdCBoZSB3YXMgYWJsZSBjb3VudCB0aGUgZ3JleSBzcXVhcmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Lbm93aW5nIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBib2FyZCBhbmQgdGhlIG51bWJlciBLIGJlZm9yZWhhbmQsIGhvd2V2ZXIsIGl0IGlzIHBvc3NpYmxlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIHJlc3VsdCBmYXN0ZXIuIFRoaXMgaXMgeW91ciB0YXNrLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIFIgKDEgJmxlOyBSICZsZTsgMSAwMDAgMDAwKSBhbmQgQyAoMSAmbGU7IEMgJmxlOyAxIDAwMCAwMDApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgYm9hcmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBLICgxICZsZTsgSyAmbGU7IFImbWlkZG90O0MpLCB0aGUgdG90YWwgbnVtYmVyIG9mIHNxdWFyZXMgdGhlIGhlZGdlaG9nIHZpc2l0cy4gTm90ZSB0aGF0IHRoaXMgbnVtYmVyIG1heSBub3QgZml0IGluIGEgMzItYml0IGludGVnZXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2YgZ3JleSBjZWxscyB0aGUgaGVkZ2Vob2cgdmlzaXRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==