/*
Time limit: 3000ms
Memory limit: 256mb

---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define DEFAULT_VALUE -1

// Notice: Now each node in the list has an additional field `pos` to store the position of the element in the array (0-indexed)
struct listNode {
  int value;
  int pos;
  struct listNode *next;
  struct listNode *prev;
};

typedef struct listNode *ListNode;

ListNode allocateEmptyListNode(void) {
  ListNode newNode = (ListNode)malloc(sizeof(struct listNode));
  newNode->value = DEFAULT_VALUE;
  newNode->pos = DEFAULT_VALUE;
  newNode->next = NULL;
  newNode->prev = NULL;
  return newNode;
}

void freeListNode(ListNode node) { free(node); }

struct list {
  struct listNode *head;
  struct listNode *tail;
};

typedef struct list *ListADT;

ListADT createList(void);
void deleteList(ListADT list);
int isEmptyList(ListADT list);
void insertInPlace(ListADT list, ListNode p, int value, int pos);
void insert(ListADT list, int value, int pos);
void delete(ListADT list, ListNode p);

ListADT createList(void) {
  ListADT list = (ListADT)malloc(sizeof(struct list));
  list->head = allocateEmptyListNode();
  list->tail = allocateEmptyListNode();
  list->head->next = list->tail;
  list->tail->prev = list->head;
  return list;
}

int isEmptyList(ListADT list) 
{ 
  return list->head->next == list->tail; 
}

void deleteList(ListADT list) {
  while (isEmptyList(list) == 0) {
    ListNode current = list->head->next;
    list->head->next = current->next;
    current->next->prev = list->head;
    freeListNode(current);
  }
  freeListNode(list->head);
  freeListNode(list->tail);
  free(list);
}

// Notice: The position of the new element is determined by the parameter `pos`
void insertInPlace(ListADT list, ListNode p, int value, int pos) 
{
  // WRITE YOUR CODE HERE

}

// Notice: The position of the new element is determined by the parameter `pos`
void insert(ListADT list, int value, int pos) 
{ 
  // WRITE YOUR CODE HERE

}

void delete(ListADT list, ListNode p) 
{
  // WRITE YOUR CODE HERE

}

struct stack {
  ListADT List;
};

typedef struct stack *StackADT;

StackADT createStack(void);
void deleteStack(StackADT stack);
int isEmpty(StackADT stack);
int isFull(StackADT stack);
void push(StackADT stack, int value, int pos);
void pop(StackADT stack);
int top_value(StackADT stack);
int top_pos(StackADT stack);

StackADT createStack(void) {
  StackADT stack = (StackADT)malloc(sizeof(struct stack));
  stack->List = createList();
  return stack;
}

void deleteStack(StackADT stack) {
  while (!isEmpty(stack)) {
    pop(stack);
  }
  free(stack);
}

int isEmpty(StackADT stack) { return isEmptyList(stack->List); }

int isFull(StackADT stack) {
  (void)stack;
  return 0;
}

// Notice: The position of the new element is determined by the parameter `pos`
void push(StackADT stack, int value, int pos) {
  // WRITE YOUR CODE HERE

}

void pop(StackADT stack) {
  // WRITE YOUR CODE HERE

}

// Return the value of the top element in the stack
int top_value(StackADT stack) {
  // WRITE YOUR CODE HERE

}

// Return the position of the top element in the stack (0-indexed)
int top_pos(StackADT stack) {
  // WRITE YOUR CODE HERE

}

// Use the stack ADT to solve the problem
int solve(int n, int m, int** a)
{
    int sum = 0;
    // WRITE YOUR CODE HERE

}

// DO NOT MODIFY THE CODE BELOW
int main(void) {
  int n, m;
  scanf("%d%d", &n, &m);

  int** a = (int**)malloc(sizeof(int*) * n);
  for (int i = 0; i < n; ++i) {
    a[i] = (int*)malloc(sizeof(int) * m);
    for (int j = 0; j < m; ++j) {
      scanf("%d", &a[i][j]);
    }
  }
  printf("%d\n", solve(n, m, a));
  return 0;
}


---------------------------------------End of Code---------------------------------------

## Largest Rectangle of 1s in Binary Matrix 

Given an $n x m$ binary matrix (a matrix consisting only of 0s and 1s), your task is to find the largest rectangular submatrix that is filled entirely with 1s. Calculate and output the area of this largest submatrix (area = width × height).

**Hint**: Solve the problem by maintaining a monotonic increasing stack.

### Input

First line contains two integers $n$ and $m$ ($1 \leq n,m \leq 3000$), representing the number of rows and columns of the matrix, respectively.

The next $n$ lines each contain $m$ space-separated integers (either 0 or 1), representing the rows of the binary matrix.

### Output

Output a single integer: the area of the largest all-1 rectangular submatrix in the given matrix.

### Example

**Input**
4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

**Output**

6

**Explanation**

The largest rectangular submatrix that is filled entirely with 1s is [2-3, 3-5].