题目背景

在父亲以撒临终之时，雅阁用一碗红豆汤骗走了长子权，因而与哥哥以扫决裂。在躲避以扫追杀时，他纵身跃入地下室并昏迷了过去。等他醒来时，发现手中握着一把红钥匙……

“我要把天国的钥匙给你。”

              —— 《马太福音》第16章第19节

题目描述

雅阁初始处在地图中的初始房间中，地图可看做$n\times m$的网格图，地图中散落着q个普通房间和1个初始房间和1个boss房间。每个房间都占据一格格子。

红钥匙有神奇的魔力，可以在当前房间旁生成一个红房间，并打开该红房间相邻的所有普通房间的门(如下图，每次可以打开绿色普通房间旁边四个房间之一)

但是红钥匙最多只能使用p次，否则会召唤出可怕的哥哥以扫。幸运的是，雅阁通过秘密之书知晓了所有普通房间的位置，以及每个普通房间的内容。同时，红房间是不稳定的，离开红房间后要想再返回，需要再使用一次红钥匙。

每个普通房间的内容都是不一样的，有的房间有道具，有的房间有一群蜘蛛。因此雅阁给每个普通房间都设定了一个权值wi，到达该房间能获得wi的价值,不能不取。特殊的，初始房间、红房间与boss房没有权值。

雅阁还有一项能力，他可以从任意一个房间传送到已到达过的初始房间、boss房或普通房间，但不能传送到红房间。此过程不消耗充能。

现在雅阁想知道，从初始房间开始，在使用红钥匙次数不超过p次的前提下，到达boss房能获得的最大价值。

Format

输入格式

第一行1个整数T,表示有T组数据 对于每组数据，第一行八个整数 $n,m,sx,sy,tx,ty,p,q$分别表示网格图范围为$n$行$m$列，初始房间横坐标、纵坐标，boss房横坐标、纵坐标，红钥匙充能数、除初始房间与boss房之外的普通房间个数。 下面q行，每行三个整数$xi,yi,wi$,表示第$i$个普通房间的横坐标、纵坐标与权值。

输出格式

对于每组数据，输出一行一个整数，表示此层能获得的最大总价值。

特殊的，当雅阁到达不了boss房,或到达boss房时取得的最大总价值为负数时时，输出“hungry”。

样例

2
7 10 2 3 6 9 11 6
6 2 10
5 5 5
4 6 -1
1 8 3
2 10 2
4 10 7
6 9 2 4 5 8 9 5
5 2 10
4 5 3
3 6 -1
1 8 7
3 9 4

15
14

提示说明

对于样例1第一组数据，如图，红色块表示初始房间位置，绿色块表示boss房位置，标有数字房间表示普通房间，其余为红房间。蓝色线为答案的一条最优路径，总共消耗11点充能。到达权值为10与5的普通房间。

对于样例1第二组数据，如图，蓝色线为答案的一条最优路径，总共消耗9点充能。路线为:初始房间->权值为3的普通房->boss房->权值为4的普通房->权值为7的普通房。最终再传送回boss房结束本层。

对于10%的数据，$n,m\le2$

对于另外20%的数据，$n=1$或$m=1$

对于50%的数据，$wi>0$

对于100%的数据，$1\le T\le5,1\le sx,tx,xi\le n\le100,1\le sy,ty,yi\le m\le100, 1\le p\le n\times m,1\le q\le 15,-10^7\le w\le 10^7$