Write an efficient algorithm that searches for a value target in an m x n integer matrix. Each row is sorted left to right and each column is sorted top to bottom.

Example:

Input:
3 4
1 4 7 11
2 5 8 12
3 6 9 16
Target: 5
Output: true

Input format: Line 1: m n. Next m lines: n space-separated integers. Last line: target.

Output format: true or false.