切蛋糕 Cake slicing

翻译：有一个n行m列(1<=n,m<=20)的网络蛋糕上有k个樱桃。每次可以用一刀沿着网络线把蛋糕切成两块，并且只能够直切不能拐弯。要求最后每一块蛋糕上恰好有一个樱桃，且切割线总长度最小。 输入输出格式 输入格式:每次输入有若干组数据。每组数据第一行有三个正整数n m k(行，列，樱桃个数)，之后的k行每行两个正整数(樱桃的坐标) 输出格式:输出有若干行，对应每组数据。每行输出两个正整数(id,最小的切割长度) 输入输出样例 输入样例: 3 4 3 1 2 2 3 3 2 输出样例: Case 1: 5

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4504 [PDF](https://uva.onlinejudge.org/external/16/p1629.pdf)