732. Count negative elements in sorted matrix

0

Easy

Given a matrix with M rows and N columns, where the elements are sorted in ascending order both row-wise and column-wise, determine the total count of negative elements in the matrix. The solution should have a time complexity of O(N).

Input Format

The input consists of two integers, M and N, representing the number of rows and columns in the matrix. This is followed by M*N elements of the matrix.

Output Format

The output should be a single integer representing the count of negative numbers in the matrix.

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