题目描述

一天，波咖正在和狗狗玩游戏，在一张大小为$n\times m$个格子的地图中，波咖在每个格子上都设计了伤害为$a_{i,j}$的陷阱。狗狗一开始有$k$点生命值，狗狗的获胜条件就是从$\left ( 1,1\right )$进入地图然后活着从$\left ( n,m\right )$离开。因为狗狗很贴心，所以他决定让着波咖，他保证自己只会往右或往下移动。而波咖却很坏，尽管知道狗狗让着他了，他也不希望狗狗有太大的胜率。现在请你帮波咖判断狗狗是否有多条不同路径能够胜利。如果有请输出“Yes”，波咖会重新设计关卡，如果没有请输出“No”,不保证一定有多条不同路径。

当狗狗在进入伤害为$a_{i,j}$的陷阱后，生命值就会减少该值。当狗狗生命为$0$或更低时，狗狗就输了。

当且仅当两条路径中狗狗走过格子完全相同时，他们会被认为是相同的路径。

输入格式

第一行包含三个整数$n$,$m$$(1\leq n,m\leq 10^3)$,$k$$(1\leq k\leq 10^9)$分别表达地图的长，宽和狗狗的生命值。

接下来输入一个$n \times m$的矩阵，其中$a_{i,j}(1\leq a_{i,j}\leq 10^5)$表示在第$i$行第$j$列的陷阱伤害。

输出格式

如果有多条不同的路径能够让狗狗胜利请输出"Yes"，否则输出"No"。

样例

2 2 4 
1 1 
1 1

Yes

2 2 4 
1 1 
2 1

No

2 2 3 
1 1 
1 1

No

提示

样例一中，狗狗的不同路径总共有两条，而且都没有在路上死亡，故输出Yes。

样例二中，狗狗的不同路径总共有两条，但有一条路径中，狗狗死在了终点，没有成功离开，故狗狗获胜的路径只有一条输出No。

样例三中，狗狗的不同路径总共有两条，而且都有在路上死亡，故输出No。

明确波咖是知道狗狗让着自己的，在波咖眼中狗狗也只会向下或向右且不会掉出地图，因为有空气墙。