CF598E Chocolate Bar

你有一块长方形的巧克力，这块巧克力共有n*m小块。你想吃k小块巧克力，因此你也许需要掰开这块巧克力。 在每一次操作中你可以把任意一块矩形形状的巧克力掰成两块矩形形状的巧克力。你只能沿着巧克力小块之间的分割线掰开巧克力——可以沿着水平方向或是竖直方向掰开。掰开巧克力的花费等于分割线长度的平方。 例如，如果你有一块2*3的巧克力，那么你可以沿着水平方向掰从而得到两块1*3的巧克力，这次操作的花费即为3^2=9。或者你也可以沿着竖直方向掰从而得到一块2*1的巧克力和一块2*2的巧克力，这次操作的花费即为2^2=4。 对于每一个给出的n，m和k，计算出最小花费。你可以用多块巧克力凑出k小块巧克力。剩余的巧克力可以不是完整的一块。

无

无

在样例一的第1行这组数据情况下一共需要进行2次操作： 1.把2*2的巧克力掰成两块2*1的巧克力，花费为2^2=4； 2.把2*1的巧克力掰成两块1*1的巧克力，花费为1^2=1。 在样例一的第2行这组数据情况下操作步骤同上。 Translated by @radish布団