You are shepherding near ancient Bethlehem when you hear that Jesus is born! Unfortunately, you are the last of your fellow shepherds to go and the ~K~ sheep that the shepherds are supposed to watch are still scattered around the field.
The field can be represented as an ~R~ meters by ~C~ meters grid where each square in the grid represents ~1~ m2 of grass. You have to herd the sheep into an area as small as possible, but each sheep needs to remain in the field and needs an entire square for itself. Afterward, you will erect a temporary fence around the sheep along the grid lines. What is the minimum length of fence, in meters, required?
The first line of input will contain two space separated integers, ~R~ and ~C~ ~(1 \le R, C \le 10^9)~.
The second line of input will contain a single integer, ~K~ ~(1 \le K \le R \cdot C)~.
For 20% of the points, ~1 \le R, C \le 50~.
For another 20% of the points, ~1 \le R, C \le 1\,000~.
For another 30% of the points, ~1 \le R, C \le 10^6~.
Note: It is recommended to use 64-bit integers to compute the solution (
long long in C++,
long in Java,
int64 in Pascal).
Output a single integer, the minimum length of fence, in meters, required to surround the sheep.
5 5 14
Explanation for Sample Output
You can herd the sheep like this, where
. represents an empty square and
* represents a square with one sheep:
****. ****. ***.. ***.. .....
This requires ~4+4+3+2+1+2 = 16~ meters of fencing.