Search Sorted Grid

You are given an m x n integer matrix matrix where every row is sorted in ascending order from left to right and every column is sorted in ascending order from top to bottom, plus an integer target.

Return true if target appears in the matrix, false otherwise.

You must write an algorithm that runs in $O(m + n)$ time.

Examples

Example 1

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false