U498123 sans审判战
题目背景
“外面的天气真好，鸟儿在歌唱，花儿在绽放，像你这样的孩子，就应该
# 在~地~狱~里~焚~烧”
sans将视线从窗外收回，疲惫的眼神中藏着些许淡淡的忧伤，“孩子，这就是你的选择吗？”
## *你保持沉默。。。。
随着黑暗袭来，绿色和蓝色交融的审判之火在黑暗中散发着渗人的微光。
2024/10/1 正经一点了，应该不影响题意理解了（大概）；
题目描述
sans审判战开始了！激情的审判乐响起，作为屠杀线的玩家，积累的LV让你有了 m 的生命值上限，你无所畏惧，但作为一个高玩，你不愿局限于此，~~但是你做不到无伤（技术问题）~~
有 n 个回合，每个回合你会在一个 $a \times b$ 的矩阵里接受审判，从矩形的一角到另一角，每个点都会有一个伤害值 q ，每过这样一个点都会扣除相应生命值，你要保证中途不能死亡（即生命值不能小于等于0）
由于sans有审判眼，他的重力攻击会使你每回合只能向固定的两个方向移动。
每回合过后（除最后一回合），你有两种操作：
1. 回血，你开局就会拥有 h 个食物，每个食物都有一个回复量，使用第 k 种食物会回复 $g_k$ 的血量，但回复的血量若超出生命上限，不会获得额外血量（不超过生命上限）
2. 饶恕，如果你对sans进行饶恕，sans会回想起一些以前的美好回忆，看你这么菜，他会放点水。即使下个回合内矩形所有高于你当前生命值一半（若有除后小数向下取整）的伤害值减去 p ，每个回合都有一个 p 值。（第一回合的p值没啥用，别理了）
#### 注：每次只能进行一种操作，每次回血只能吃一种食物。
撑过最后一个回合吧！
若有可行方案，求剩余食物的回复量之和的两倍与当前剩余生命值之和的最大值。
若无可行方案，输出最多能撑过的回合数。
输入格式
#### 第一行，输入 n ，m ，h ，分别表示回合数，生命值上限，食物数。
#### 第二行 h 个数据，表示食物的回复量。
#### 第三行 n 个数据，分别是每个回合的饶恕 p 值。
### 以下 n 组数据：
第一行输入 a，b，表示矩阵的行和列。
第二行输入 $x_1，y_1$，表示起始点，$x_2，y_2$，表示终点，输入两个重力方向，其中1表示左，2表示右，3表示下，4表示上。
以下a行b列，为伤害值分布。第i行第j列的伤害值为$q_{ij}$。
输出格式
__第一行一个数字。__
#### 若有可行方案，求剩余食物的回复量之和的两倍与当前剩余生命值之和的最大值。
#### 若无可行方案，输出最多能撑过的回合数。
说明/提示
样例2解释：
第一回合走最优解，扣除23点生命值，HP=73，
然后吃一个回10血的食物，PH=83，
第二回合走最优解，扣除54点生命值，PH=29，
然后吃一个回20血的食物，PH=49，
第三回合走最优解，扣除45点血，PH=4，
吃一个回10血的食物，PH=14，
第四回合走最优解，扣除4点血,PH=10,
最终，剩下一个10血的食物，PH剩10，
$答案=10 \times 2+10=30$
# 数据保证
方向1和2，方向3和4不会同时出现
并且伤害中无负权值出现，初始点和终点无伤害值；
$n\le10$,
m$\le10^8$;
$h\le15$;
$a,b\le100$;
q$\le10^8$;p$\le3 \times10^5$;