Row with the most 1s

Given a grid of 0s and 1s, print the row number (starting from 1) that has the most 1s. If rows tie, print the smallest row number. If the grid has no 1s at all, print -1.

Reported in: TCS NQT (Sep 2023) (memory-based)

Input

First line: R and C. Next R lines: C values (0 or 1).

Output

A row number, or -1.

Constraints

1 ≤ R, C ≤ 1000.

Example 1

Input:
3 4
0 1 1 0
1 1 1 0
0 0 0 1

Output:
2

Example 2

Input:
2 2
0 0
0 0

Output:
-1

Hint: Sum each row and remember the first row with the biggest sum.

All coding practice