Given a rows x cols binary matrix filled with '0's and '1's, find the largest rectangle containing only '1's and return its area.

Examples

Example 1

Input:  matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

┌───┬───┬───┬───┬───┐ │ 1 │ 0 │ 1 │ 0 │ 0 │ ├───┼───╔═══╦═══╦═══╗ │ 1 │ 0 ║ 1 ║ 1 ║ 1 ║ ├───┼───╠═══╬═══╬═══╣ │ 1 │ 1 ║ 1 ║ 1 ║ 1 ║ ├───┼───╚═══╩═══╩═══╝ │ 1 │ 0 │ 0 │ 1 │ 0 │ └───┴───┴───┴───┴───┘Output: 6 (double-line border = maximal rectangle, 3 × 2)

Example 2

Input:  matrix = [["0"]]
Output: 0

Example 3

Input:  matrix = [["1"]]
Output: 1

Constraints

• rows == matrix.length
• cols == matrix[i].length
• 1 <= rows, cols <= 200
• matrix[i][j] is '0' or '1'