339. Count negative elements in sorted matrix

0

Easy

Given an M x N matrix, which is row-wise and column-wise sorted, count the total number of negative elements present in it in linear time.

Input Format

Two input integers M and N denoting number of rows and columns

M*N elements of the matrix.

M*N elements of the matrix.

Output Format

Count of negative numbers

Example

Input

4 5
-7 -3 -1 -3 5
-3 -2 2 4 6
-1 1 3 5 8
3 4 7 8 9

Output

7

Constraints

0<=M,N<=50

-100<=mat[i][j]<=100

Time Complexity Expected: O(N)

-100<=mat[i][j]<=100

Time Complexity Expected: O(N)

Loading...

View Submissions

Console