1155: 大秦宝藏

大秦宝藏在一个神秘的古墓里面，古墓由20000行和20000列的正方形网格构成，每个网格代表1个墓室，在某些墓室里藏有宝藏称为宝藏点（用黑色实心圆点表示），如图1所示。

  图1 大秦古墓简图                           图2 简图对应的行走方案  

要想盗取这些宝藏，必须遵守如下大秦盗墓法则： 

1. 某个指定的墓室是魔法之门，只能从魔法之门进出古墓；
2. 魔法之门在某个宝藏点位置；
3. 任意墓室都只可以从左、右、上、下四个方向之一前往旁边的墓室，如果旁边存在墓室的话；
4. 从魔法之门进入墓室后只能往前走，不可以走回头路。且再一次回到魔法之门时必须出古墓；
5. 从魔法之门出发后必须经过所有的宝藏点并回到魔法之门，才能成功获得这些宝藏；
6. 从前一宝藏点A到下一宝藏点B所形成的路线必须为直线，且在B点必须改变前进方向到下一宝藏点C。即A、B、C不可以在一条直线上，如图2所示；
7. 每个宝藏点的宝藏价值取决于首次离开此宝藏点的方向，即从左、右、上、下四个方向离开对应的价值不同；
8. 除了魔法之门对应的墓室可以作为终点再次进入1次，其它任何墓室最多只能经过1次；
9. 古墓必定存在至少一条满足如上规则的行走路线。

假如你是一个出色的摸金校尉，你能按照大秦盗墓法则盗取到价值最多的宝藏吗？ 

输入有多组（不超过100）测试实例。

每组测试实例的第一行为两个正整数N、M（4 ≤ N ≤ 50，1 ≤ M ≤ N），分别代表宝藏点的数量（宝藏点按输入顺序编号为1到N）和魔法之门宝藏点所对应的编号，即古墓的入口。

接下来的N行代表N个宝藏点的数据。每个宝藏点数据（每行）包含六个整数，前两个整数以“X,Y” (1 ≤ X,Y ≤ 20000)的形式给出宝藏点的坐标（假设左下角墓室的坐标为[1,1]，右上角为[N,N]）；后四个整数（大于0，小于等于100）分别表示从左、右、上、下四个方向离开宝藏点时宝藏点所对应的价值。

请注意：这些宝藏点是按任意顺序给出的，所有宝藏点的坐标都不同。

输入结束将由一个N和M均等于0的测试实例表示，不应处理此测试实例。

       每组测试实例输出一行，格式为：“Case i: sum”，其中i是测试实例的编号（从1开始），sum为按照大秦盗墓法则盗取的宝藏的最大价值。

4 1
1 1 1 2 8 8
2 2 2 2 9 4
1 2 8 3 1 7
2 1 1 5 1 6
6 4
3 3 6 2 5 1
5 5 1 8 2 9
1 3 8 1 9 1
3 1 4 5 9 4
1 5 1 9 2 3
5 1 3 2 6 2
0 0

Case 1: 16
Case 2: 45