{"raw_statement":[{"iden":"problem statement","content":"There are $N$ squares arranged in a row, numbered $1$ to $N$ from left to right. Initially, all squares are white.\nYou can perform the following $M$ types of operations **any number of times in any order**:\n\n*   Type-$i$ operation: Paint square $L_i$ through square $R_i$ in black.\n\nFind 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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 500$\n*   $1 \\leq M \\leq N(N+1)/2$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   $(L_i,R_i) \\neq (L_j,R_j)$ for all $i \\neq j$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_M$ $R_M$"},{"iden":"sample input 1","content":"3 3\n1 3\n1 1\n3 3"},{"iden":"sample output 1","content":"3\n\nIf you perform the operations as follows, they will change the state of the squares three times.\n\n*   Perform type-$2$ operation. Square $1$ is newly painted black.\n*   Perform type-$3$ operation. Square $3$ is newly painted black.\n*   Perform type-$1$ operation. Square $2$ is newly painted black."},{"iden":"sample input 2","content":"4 3\n1 2\n3 4\n1 4"},{"iden":"sample output 2","content":"2"},{"iden":"sample input 3","content":"5 5\n4 5\n1 1\n2 4\n1 2\n2 5"},{"iden":"sample output 3","content":"4"},{"iden":"sample input 4","content":"20 15\n2 4\n16 19\n7 13\n1 15\n3 18\n10 11\n1 10\n1 7\n14 16\n1 16\n2 17\n1 17\n12 14\n3 17\n4 10"},{"iden":"sample output 4","content":"11"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}