Identify the Optimal Seating Row

You are given a seating chart of a theater represented as a matrix with n rows and m seats in each row. In the chart, a value of 1 indicates an available seat and 0 indicates an occupied seat. Given a group size k, your task is to determine the row number (1-indexed) which can accommodate the group in a contiguous block of seats, and among those, the row with the maximum number of consecutive available seats. If no row can accommodate the group, output -1.

The condition you need to satisfy for a row is that it has at least k consecutive available seats, i.e. if we denote the number of consecutive available seats as \(c\), then \(c \ge k\). If multiple rows qualify, choose the row having the longest consecutive block. If there is a tie, the earliest row (lowest row number) encountered should be selected.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers separated by space: n (number of rows) and m (number of seats per row).
• The next n lines each contain m integers (each 0 or 1) separated by space representing the seating chart.
• The last line contains an integer k, the size of the group.

For example:

4 5 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 3

outputFormat

Output to standard output (stdout) a single integer representing the row number that can accommodate the group with the maximum consecutive available seats. If no such row exists, output -1.## sample

4 5
1 0 0 1 1
1 1 1 0 1
0 0 1 1 1
1 1 1 1 1
3

4