Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Crosses

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere is a board with a grid consisting of *n* rows and *m* columns, the rows are numbered from 1 from top to bottom and the columns are numbered from 1 from left to right. In this grid we will denote the cell that lies on row number *i* and column number *j* as (*i*, *j*).

A group of six numbers (*a*, *b*, *c*, *d*, *x*_{0}, *y*_{0}), where 0 ≤ *a*, *b*, *c*, *d*, is a cross, and there is a set of cells that are assigned to it. Cell (*x*, *y*) belongs to this set if at least one of two conditions are fulfilled:

- |
*x*_{0}-*x*| ≤*a*and |*y*_{0}-*y*| ≤*b* - |
*x*_{0}-*x*| ≤*c*and |*y*_{0}-*y*| ≤*d*

Your task is to find the number of different groups of six numbers, (*a*, *b*, *c*, *d*, *x*_{0}, *y*_{0}) that determine the crosses of an area equal to *s*, which are placed entirely on the grid. The cross is placed entirely on the grid, if any of its cells is in the range of the grid (that is for each cell (*x*, *y*) of the cross 1 ≤ *x* ≤ *n*; 1 ≤ *y* ≤ *m* holds). The area of the cross is the number of cells it has.

Note that two crosses are considered distinct if the ordered groups of six numbers that denote them are distinct, even if these crosses coincide as sets of points.

Input

The input consists of a single line containing three integers *n*, *m* and *s* (1 ≤ *n*, *m* ≤ 500, 1 ≤ *s* ≤ *n*·*m*). The integers are separated by a space.

Output

Print a single integer — the number of distinct groups of six integers that denote crosses with area *s* and that are fully placed on the *n* × *m* grid.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

2 2 1

Output

4

Input

3 4 5

Output

4

Note

In the first sample the sought groups of six numbers are: (0, 0, 0, 0, 1, 1), (0, 0, 0, 0, 1, 2), (0, 0, 0, 0, 2, 1), (0, 0, 0, 0, 2, 2).

In the second sample the sought groups of six numbers are: (0, 1, 1, 0, 2, 2), (0, 1, 1, 0, 2, 3), (1, 0, 0, 1, 2, 2), (1, 0, 0, 1, 2, 3).

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/20/2021 15:39:28 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|