题目背景

你从昏迷睁开眼，发现自己置身于缅北关押所，也许是你编程能力太强被抓去写爬虫了吧，你通过一些不明手段获取到了这里的地图，现在你需要逃出这里，尽快回国

题目描述

给定一张 $n \times m$ 的地图，右下角为出口，其中

• 0表示空地，可以通过
• 其他非0数字 $k$ 代表一个缅北守卫，不会移动，碰到Ta则会被嘎腰子，减少 $k$ 点生命值
• -1表示障碍物，不可通过

已知你的初始位置在左上角，初始生命值为 $x$，请问你能不能活着（即生命值始终大于0）并走到右下角，如果可以请输出走出来后的最大生命值和保证生命值最大的最小所需步数，否则输出Doomed to die!

输入格式

第一行两个正整数 $n$ 和 $m$

接下来 $n$ 行每行 $m$ 个数字或字符，以空格隔开

最后一行一个正整数 $x$，表示生命值

输出格式

一行一个正整数或一个字符串

样例

3 3
0 5 0
2 -1 3
0 0 0
10

8 4

数据范围

对于$100\%$的数据：$1 ≤ n, m ≤ 20，1 ≤ k ≤ 1000，1 ≤ x ≤ 10^4$