题目描述

Lazar 已经成为了一名首席建筑师。他受邀为 Kolelandia 的一栋新宿舍楼设计某一层的房间布局。给定一个楼层平面，他需要用墙把它分成若干独立房间。每一堵新建的墙都必须与楼层外墙平行。

你可以把楼层平面看成一个大小为 $N\times M$ 的矩形。每个房间都是一个更小的矩形，尺寸为 $a\times b$，并且位于大矩形内部。整个楼层必须被房间完全覆盖；任意两个房间的内部不能相交，但可以共边或共点接触。

此外，每个房间都必须至少有一条边与整个楼层大矩形的某一条外墙重合。这样房间就可以通过外墙安装窗户而获得采光。

下面是两个示例布局，左图是合法的，右图是不合法的。

所有房间的面积都应尽量接近 $K$。对于一个尺寸为 $a\times b$ 的房间，定义它的面积偏差为

整个楼层布局的偏差为所有房间面积偏差之和。

请你编写程序 architecture，求一个合法建筑布局的最小总偏差。

输入格式

输入一行，包含三个整数 $N,M,K$，分别表示大矩形的尺寸以及理想房间面积。

输出格式

输出一个整数，表示合法建筑布局的最小总偏差。

数据范围

• $1\le N,M\le 300$；
• $1\le K\le 10000$。

子任务

只有通过某个子任务中的所有测试点，才能获得该子任务分数。

样例

样例 1

3 3 2

1

样例 2

2 2 2

0

样例 3

2 3 4

2