You are given an m × n integer matrix where each row is sorted left to right, and the first integer of each row is greater than the last of the previous row. Given a target, return true if it exists in the matrix.

Example 1:

Input:
3 4
1 3 5 7
10 11 16 20
23 30 34 60
Target: 3
Output: true

Constraints:

• m == matrix.length, n == matrix[i].length
• 1 ≤ m, n ≤ 100
• -10⁴ ≤ matrix[i][j], target ≤ 10⁴

Input format: First line: m n. Then m rows of n integers. Last line: target.

Output format: true or false