Search a 2D Matrix II

Problem statement

A climate table orders measurements from left to right within each row and from top to bottom within each column. The ranges of different rows may overlap, so a lookup must use both sorting rules rather than treating the table as one sorted sequence. Your task Determine whether target appears in a matrix whose rows and columns are each sorted in nondecreasing order. Aim for O(rows + columns) time. Important details Duplicate measurements are permitted. The first value of a new row need not exceed the last value of the previous row. An unsuccessful search must return false even when target lies within the overall minimum and maximum. Worked example In rows [1, 4, 7] and [2, 5, 9], target 2 is present on the second row. The flattened sequence is not sorted, but the row and column rules both hold.

Input format

First line: rows columns target. Next rows lines: the matrix.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= rows, columns <= 300; -1000000000 <= values, target <= 1000000000.

Sample input

2 3 2
1 4 7
2 5 9

Sample output

true