背景

(以下情节纯属出题人主观YY虚构。)2033年3月3日,农历二月初三,《名探侦コナン》连载到了第233卷!在这一卷的第2333集里,Haibara Ai 研制出了APTX4869的解药,Kudou Shinichi 终于又回到了Lan的身边。与此同时,Lan 对于Conan 的消失感到越来越疑惑。两个多月后就是Lan 的生日了,Shinichi 决定在她生日那天吐露真相。

描述

在Moli Lan生日那天,Kudou Shinichi送给她一套名叫《名探侦コナン》的漫画(= =|),对这本书爱不释手的Lan 不忍心一次把它读完,于是她每天晚上都会读上几页。Lan 读书的方法非常特别。 《名探侦コナン》一共M页,起初所有页都是没有标记的。第i天读书时,Lan 会手持一根颜色为i的水彩笔,并把这一天读过的页标记为颜色i。她每天选择一个区间[L,R],阅读在[L,R]中所有从未读过(没有标记)的页,以及[L,R]中所有与第L页上的标记颜色相同的页。读过的这些页会被重新标记颜色(颜色可以覆盖)。N天之后,Lan 想知道她一共读过了多少页书呢?

输入格式

第一行两个整数M、N。

接下来N行,每行两个整数L、R。第i+1行的两个数表示Lan 第i天选择的区间。

输出格式

一个整数,表示Lan 一共读了多少页书。

样例输入

15 5
1 6
4 8
2 7
10 12
7 13

样例输出

20

数据范围与约定

  • 对于20%的数据,1<=n,m<=1000。
  • 对于50%的数据,1<=n<=1000,1<=m<=100000。
  • 对于100%的数据,1<=n,m<=300000,1<=L<=R<=m。

样例解释

第一天读1~6页,标记上颜色1。第二天读4~8页,其中56和4颜色相同均为1,78未被标记,4~8读完后标记上颜色2。第三天读23两页,因为2~7中都有标记且只有3和2颜色一样,读完后2~3标记颜色为3。第四天读10~12页,标记上颜色4。第五天读789、13页,13页没有标记,89也和7页的颜色相同,读完后789、13标记颜色5。一共读了6+5+2+3+4=20页书。