D - Maximize Update Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

N 個のマスが横一列に並んでおり，左から順に 1 から N の番号がついています． 最初，すべてのマスは白色です．

あなたは以下の M 種類の操作を好きな順序で好きな回数行うことができます．

  • i 種類目の操作: マス L_i からマス R_i までを黒色で塗る．

マス目の状態を変化させるような操作の回数の最大値を求めてください． なお，操作を行った結果色が変化したマスが 1 つでもあれば，その操作はマス目の状態を変化させたとみなします．

制約

  • 1 \leq N \leq 500
  • 1 \leq M \leq N(N+1)/2
  • 1 \leq L_i \leq R_i \leq N
  • (L_i,R_i) \neq (L_j,R_j) (i \neq j)
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

出力

答えを出力せよ．

入力例 1

3 3
1 3
1 1
3 3

出力例 1

3

以下のように操作すると，マス目の状態を変化させる操作が 3 回行われます．

  • 2 種類目の操作を行う．新たにマス 1 が黒色で塗られる．
  • 3 種類目の操作を行う．新たにマス 3 が黒色で塗られる．
  • 1 種類目の操作を行う．新たにマス 2 が黒色で塗られる．

入力例 2

4 3
1 2
3 4
1 4

出力例 2

2

入力例 3

5 5
4 5
1 1
2 4
1 2
2 5

出力例 3

4

入力例 4

20 15
2 4
16 19
7 13
1 15
3 18
10 11
1 10
1 7
14 16
1 16
2 17
1 17
12 14
3 17
4 10

出力例 4

11

Score : 700 points

Problem Statement

There are N squares arranged in a row, numbered 1 to N from left to right. Initially, all squares are white.

You can perform the following M types of operations any number of times in any order:

  • Type-i operation: Paint square L_i through square R_i in black.

Find the maximum number of times the operations can change the state of the squares. If an operation changes the color of at least one square, that operation is considered to change the state of the squares.

Constraints

  • 1 \leq N \leq 500
  • 1 \leq M \leq N(N+1)/2
  • 1 \leq L_i \leq R_i \leq N
  • (L_i,R_i) \neq (L_j,R_j) for all i \neq j
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

Print the answer.

Sample Input 1

3 3
1 3
1 1
3 3

Sample Output 1

3

If you perform the operations as follows, they will change the state of the squares three times.

  • Perform type-2 operation. Square 1 is newly painted black.
  • Perform type-3 operation. Square 3 is newly painted black.
  • Perform type-1 operation. Square 2 is newly painted black.

Sample Input 2

4 3
1 2
3 4
1 4

Sample Output 2

2

Sample Input 3

5 5
4 5
1 1
2 4
1 2
2 5

Sample Output 3

4

Sample Input 4

20 15
2 4
16 19
7 13
1 15
3 18
10 11
1 10
1 7
14 16
1 16
2 17
1 17
12 14
3 17
4 10

Sample Output 4

11