Under construction

Still being built. Things may change

Rectangles

Time limit1sMemory limit128 MB

Summary
Count axis-aligned rectangles on an n by m grid of points whose perimeter is at least p.
Level

Easy3 of 10

Topics
Math, Brute force, Implementation
Solved
No attempts yet

Problem

How many rectangles can you find in the figure below?

In the figure above we can find 6 rectangles of size 1×11 \times 1, 4 of size 2×12 \times 1, 3 of size 1×21 \times 2, 2 of size 2×22 \times 2, 2 of size 3×13 \times 1, and 1 of size 3×23 \times 2, which gives 18 in total. Here we count only rectangles whose vertices lie on grid points (the intersections of the vertical and horizontal line segments) and whose four sides are all vertical or horizontal. The grid above has dimensions 3×23 \times 2.

And how many such rectangles with a perimeter of at least 6 are there? For this grid there are 12 of them.

Given a grid of dimensions n×mn \times m and a lower bound pp on the perimeter, count the rectangles whose vertices lie on grid points, whose four sides are vertical or horizontal, and whose perimeter is at least pp.

Input

The first and only line of the standard input contains three integers nn, mm, and pp (1≤n,m≤1001 \le n, m \le 100, 4≤p≤2(n+m)4 \le p \le 2(n+m)), representing the dimensions of the grid and the lower bound on the perimeter of the rectangles.

Output

On the first line of the standard output, print a single integer: the number of rectangles of the n×mn \times m grid whose vertices lie on grid points, whose four sides are vertical or horizontal, and whose perimeter is at least pp.

Examples2

  1. Example 1

    Input
    3 2 4
    
    Expected output
    18
    
  2. Example 2

    Input
    3 2 6
    
    Expected output
    12