U134194 Elephant在食堂

**由于出题人被自己出的题卡死，写不出std，所以目前本题只有20%数据范围的测试点，什么乱七八糟的做法都能过，希望大佬们帮忙写一下正解** 一上午的训练（~~划水~~）结束，Elephant饥肠辘辘的走到了食堂，然而他发现食堂里已经有很多的人了 假设食堂是一个$n*m$的矩阵，每个点都是一个座位，每个座位上可能有四种状态： 已经坐着人：喜欢的人，讨厌的人，以及路人甲乙丙丁，或者是空位 因为Elephant体型巨大，所以他不可能与人坐在同一个座位上，所以他一定会找到一个空位坐下，但他可以从每个座位旁经过。由于Elephant比较矫情，他希望尽可能多的经过喜欢的人，而不经过讨厌的人，而且他不喜欢多走路。 已知Elephant在（1，1）点，食堂里有a个喜欢的人，b个讨厌的人，以及c个空位，剩下的位置都路人甲乙丙丁，大家都清楚食堂的座位排布，Elephant不可能飞过桌子，所以他只会向上下左右四个方向走。 每个喜欢的人都有一个好感度$A_i$，从他身边经过的路线会得到$A_i$的满意度 Elephant绝对不会经过讨厌的人，而且经过讨厌的人周围的座位（及其坐标的周围8个点）时，满意度会减1（多个讨厌的人效果叠加） 由于Elephant实在太懒，所以每走一个座位的路程，满意度都会减1，而且他不会重复经过任何一个座位。 Elephant希望你帮他设计一个程序计算一下，他想找到一个空位坐下吃饭，能获得的最大满意度为多少？如果找不到可以坐的空位，那么Elephant就会被饿死。

以上乱七八糟的，总结如下： 给定n,m Elephant从（1，1）点开始走，不会经过讨厌的人，不会走重复的点，即，一条最令人满意的路线，一定**不包含讨厌的人**，一定**不存在重复点**，**终点**是一个**空位** 每走一步满意度减1，经过讨厌的人周围8格（以讨厌的人为中心的九宫格）满意度再减1，且多个讨厌的人效果**叠加**，经过喜欢的人，满意度增加数值等于好感度

第一行输入5个整数n,m,a,b,c 接下来a行，输入喜欢的人的坐标$x_i,y_i$以及好感度$A_i$ 接下来b行，输入讨厌的人的坐标$x_j,y_j$ 加下来c行，输入空位的坐标$x_k,y_k$

如果不能找到空位坐下，输出“The elephant starved to death” 否则输出最大的满意度

对于20%的数据，$1\leqslant n,m\leqslant9$ 对于100%的数据， $1\leqslant n,m\leqslant100$ $1\leqslant a+b+c\leqslant n*m$ 好感度$1\leqslant A_i \leqslant 100$ 由于ELephant行动迟缓，食堂里已经有很多人了，所以空座位非常少，限制在10个及以内。 保证答案在int范围内，可能为负数，空位数量可能为0，（1，1）一定是路人。 测试数据：小数据部分为人工构造，大数据为随机生成。 本题细节较多，人工数据会刻意卡一些算法 **数据范围里面对答案大小,好感度数值大小以及空位个数的限制，是为了方便一些奇奇怪怪的特殊处理和做法弄上的，完全可以去掉，还有数据范围，因为我写不出来QWQ，不知道什么算法能做，所以数据范围可能不那么有针对性，可能过小QWQ，希望大佬帮忙找一下最佳做法QWQ**