1795: 勇士的末路

    哈利是一位勇敢的屠龙勇士，他听说在西方的尽头有一头巨龙，于是决定除掉巨龙。在经过0x3f3f3f3f3f3f3f3f次对决后哈利除掉了巨龙但是他也受了重伤，巨龙的手下把哈利困在了巨龙的城堡里（巨龙的手下不敢和哈利正面对决），哈利被困在了唯一的入口他需要找到唯一的出口才可以胜利。

    城堡是一个矩形并且由n行m列个1*1的小房间组成，（x,y）表示第x行y列的房间，入口位置在（1,1）位置，出口在（n,m)位置。哈利因为和巨龙长时间战斗身上的能量只剩下w个了，而每进入一个房间都需要消耗单位1个能量（包括出入口）且哈利只能向行数或列数增加的方向移动，每个房间都有a枚金币，哈利需要收集尽量多的金币为了保证有足够的的路费回家。请问哈利是否能逃出城堡，如果能他最多可以收集多少金币。

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

20