搜索二维矩阵

题目描述

给定一个满足以下性质的 m × n 整数矩阵：

1. 每行中的整数从左到右按非递减顺序排列。
2. 每行的第一个整数大于前一行的最后一个整数。

再给定一个整数 target，请判断 target 是否在矩阵中。

输入格式

第一行输入三个整数 m、n 和 target。

接下来输入 m 行，每行 n 个整数，表示矩阵内容。

输出格式

如果 target 在矩阵中，输出 true；否则输出 false。

数据范围

1 <= m, n <= 100

-10^4 <= matrix[i][j], target <= 10^4

样例 1

输入

3 4 3
1 3 5 7
10 11 16 20
23 30 34 60

输出

true