TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

在不遠的未來,貴老師接續了薛老師的志業,執教資訊中數導論。

資訊中數導論這學期有 \(N\) 名學生,也剛好有 \(N\) 份作業。

「我貴某人這輩子只要把資訊中數導論教好就夠了」,這樣子想的貴,正開始驗收他這學期的教學成果。

貴點開了資訊中數導論公開成績的表格,這是一個 \(N \times N\) 的表格,代表著每個學生每個作業的繳交情況。

表格中每格都是 01

表格中第 \(i\) 列第 \(j\) 行是 0 代表第 \(i\) 名學生有繳交第 \(j\) 份作業。

表格中第 \(i\) 列第 \(j\) 行是 1 代表第 \(i\) 名學生缺交了第 \(j\) 份作業。 貴老師認為在表格裡的一個全部都是 0 的子矩形越大越能體現出

不過為了展現他自身的仁性,貴老師可以接受恰好一名學生的某次作業補交。

即,貴可以將表格中的某個 1 改為 0 ,不過僅限一次。

現在,貴想知道在所有可能的修改方法中(或是維持原樣),最能體現出 的方式是怎樣的。

即,貴想知道在所有可能的修改方法中(或是維持原樣),最大的全部都是 0 的子矩形能有多大?

請你告訴貴這個問題的答案吧!(你肯定不會讓貴失望的吧?)

Input Format

第一行輸入兩個正整數 $N, M$。

接下來 $M$ 行每行輸入兩個正整數 $x, y$,代表資訊中數導論公開成績的表格中第 $x$ 列第 $y$ 行是 1。任何沒被提到的格子的內容都是 0

請注意可能會有相同的 $x, y$ 限制。

  • $N\leq 5000, M\leq 10^ 6$
  • $1\leq x, y \leq N$

Output Format

輸出一個整數代表在貴修改表格後(或是維持原樣),最能體現出 的全部都是 0 的子矩形的大小。

Sample Input 1

3 3
1 1
1 3
2 2

Sample Output 1

6

Problem Source

IOICamp 2021 Day3 pF

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~10 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 1048576 65536 1 2
1 4000 1048576 65536 2
2 4000 1048576 65536 2
3 4000 1048576 65536 2
4 4000 1048576 65536 2
5 4000 1048576 65536 2
6 4000 1048576 65536 2
7 4000 1048576 65536 2
8 4000 1048576 65536 2
9 4000 1048576 65536 2
10 4000 1048576 65536 2