This page is still under construction.

Parts of this page are still being built. What you see may change.

Carrot Field

Time limit1sMemory limit1024 MB

Summary
Count lattice points within rope reach of a horse tied at the stable corner, where the rope cannot pass through the w by h rectangle.
Level

Medium7 of 10

Topics
Geometry, Math, Combinatorics, Implementation
Solved
No attempts yet

Problem

In the middle of an infinitely large carrot field there is a rectangular stable whose sides are parallel to the xx and yy axes. As in the left figure of Figure B.1, a horse is tied to the post at the lower left corner of the stable, and all four corners of the stable lie on lattice points. The distance between two lattice points that are adjacent horizontally or vertically is 11. The rope tying the horse has finite length LL. A carrot is planted at every lattice point of the carrot field. Assume the horse can eat every carrot planted within the reach of the rope.

When the stable is 11 × 6 and the rope has length 9, the carrots the horse can eat are marked with dots in the right figure of Figure B.1. The horse and the rope cannot enter the stable, and no carrots are planted on the boundary or in the interior of the stable.

Figure B.1 (left) The stable and a horse tied with a rope of length 9. (right) All carrots the horse can eat (dots).

Given the stable size w×hw \times h and the length LL of the rope tying the horse, that is, the three integers ww, hh, LL, write a program that finds the maximum number of carrots the horse can eat. Note that if the distance between a lattice point and the post is exactly LL, the horse can eat the carrot at that lattice point.

Input

The input comes from standard input. The first line gives the three positive integers ww, hh, LL (1≤w,h,L≤100,0001 \le w, h, L \le 100,000) representing the stable size and the rope length.

Output

The output goes to standard output. On the first line, print as an integer the maximum number of carrots the horse can eat under the given conditions.

Examples3

  1. Example 1

    Input
    11 6 3
    
    Expected output
    18
    
  2. Example 2

    Input
    11 6 15
    
    Expected output
    591
    
  3. Example 3

    Input
    11 6 20
    
    Expected output
    1134