Migrated from Lutece 1588 潘爷泡妹

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在一个$N \times M$的矩阵上，分布着$K$个妹子，潘爷想从中泡$Q$个最漂亮的妹子，但是一场大火夺去了潘爷的审美能力，所以他现在认为所有的妹子都是一样漂亮。潘爷的初始坐标为$(x_{0},y_{0})$，第$i$个妹子的坐标为$(x_{i},y_{i})$，泡她需要耗费$P_{i}$点体力值。潘爷为了加快泡妹速度，买了一匹马，但这匹马限制了他的行动能力。马的走法和象棋的走法一样，呈“日”字形。如果潘爷当前坐标为$(x,y)$，下一步他能到达的坐标为$(x-2,y-1),(x-2,y+1),(x-1,y-2),(x-1,y+2),(x+1,y-2),(x+1,y+2),(x+2,y-1),$ $(x+2,y+1)$。潘爷从$(x_{1},y_{1})$移动到$(x_{2},y_{2}$)需要耗费$|x_{2}-x_{1}|$点体力值，请计算潘爷泡成$Q$个妹子需耗费的最小体力值。 注：潘爷到达妹子所在的位置可以自行选择泡或不泡她，一个妹子只能泡一次。矩阵的横坐标编号为$1$$N$，纵坐标编号为$1$$M$，潘爷快马加鞭过程中不允许跳出矩阵边界。

Input

• 第一行为一个整数$T$，代表数据组数。
• 每组数据第一行为六个整数$N,M,K,Q,x_{0},y_{0}$，含义如题意所示。
• 接下来$K$行，每行三个整数$x_{i},y_{i},P_{i}$，分别代表第$i$个妹子的横坐标、纵坐标和泡她所需耗费的体力值。
• 数据范围：
• $1 \leq T,N,M,P_{i} \leq 33$
• $1 \leq Q \leq K \leq 3 \times 3$
• $1 \leq x_{0},x_{i} \leq N，1 \leq y_{0},y_{i} \leq M$
• 数据保证潘爷和$K$个妹子的坐标各不相同。

Output

输出共$T$行，对于每组数据，输出潘爷泡成$Q$个妹子需耗费的最小体力值。如果潘爷不能泡成$Q$个妹子，请输出$-1$.

Samples

2
4 4 3 2 1 1
2 3 5
4 4 3
4 1 4
2 2 1 1 2 2
1 1 1

11
-1

Note

• 第$1$组数据，潘爷从$(1,1)$移动到$(2,3)$，消耗$1$点体力值；泡妹子$1$，消耗$5$点体力值；从$(2,3)$移动到$(4,4)$，消耗$2$点体力值；泡妹子$2$，消耗$3$点体力值；最小体力值消耗为$1+5+2+3=11$.
• 第$2$组数据，潘爷无法从$(2,2)$到达$(1,1)$，所以他无法泡成$1$个妹子。

Resources

每周一题 Div1