問題文

長さ N の (,) からなる文字列 S を考えます。
以下の M 個の条件 i \ (1 \leq i \leq M)のうち、満たすことのできる条件の数は最大でいくつかを求めてください。

• 条件 i : S の L_i 文字目から R_i 文字目までを取り出した文字列は、括弧の対応が取れている文字列である。

ここで、括弧の対応が取れている文字列を、次のうちいずれかの条件を満たす文字列と定義します。

• 空文字列
• ある括弧の対応が取れている空でない文字列 s,t が存在し、s,t をこの順に連結した文字列
• ある括弧の対応が取れている文字列 s が存在し、 (, s, ) をこの順に連結した文字列

制約

• 2 \leq N \leq 500
• 1 \leq M \leq 500
• 1 \leq L_i < R_i \leq N \ (1 \leq i \leq M)
• R_i - L_i + 1 は偶数
• 入力はすべて整数

入力例 1

5 3
1 2
4 5
2 5

出力例 1

2

S= (()() のとき、1 つ目の条件は満たしませんが、 2 つ目と 3 つ目の条件を満たしています。
3 つの条件を同時に満たす S は存在しないため、満たすことのできる条件は 2 つが最大です。
S 自身は括弧の対応が取れている文字列である必要はありません。

入力例 2

2 4
1 2
1 2
1 2
1 2

出力例 2

4

同じ条件が複数ある場合もあります。

入力例 3

32 11
25 32
19 32
11 24
20 31
22 25
21 26
17 22
30 31
23 28
4 15
19 22

出力例 3

8