P4529 [SCOI2003] 切割多边形

我们希望通过切割得到一个凸 $p$ 边形，$p\le 8$。 一开始的时候，你有一个 $n\times m$ 的矩形，即它的四角的坐标分别为 $(0,0), (0,m), (n,0), (n,m)$。每次，你可以选择一条直线把当前图形切割成两部分，保留其中一个部分（另一部分扔掉），切割线的长度为此直线在多边形内部的部分的长度。 求出最短的切割线总长度。 下面是一个例子，我们需要得到中间的多边形。  分别沿着直线 $1,2,3,4$ 进行切割即可，得到中间的四边形。

无

无

样例对应于图中给出的例子。