409809: GYM103785 D Elder Ning

D. Elder Ningtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Shiwom is playing Elder Ning (the pirated version of PC game Elden Ring). He came across a level in the game where he has to choose a single sword from $$$n$$$ different swords and he has to fight against $$$m$$$ mighty monsters using that sword!!! To kill the $$$i$$$-th monster he can use any of the following swords - $$$L_{i}$$$-th, $$$L_{i}+1$$$-th, ...., $$$R_{i}-1$$$-th, $$$R_{i}$$$-th.

Out of the $$$n$$$ swords, Shiwom would only choose that one for his battle which is capable of killing all of the monsters. So your task is to find the number of swords which are capable of killing all the monsters.

Input

The first line of input contains integers $$$n$$$ and $$$m$$$ $$$(1 \leq n,m \leq 10^{5})$$$ – the number of swords and number of monsters respectively.

Each of the next $$$m$$$ lines of input contain integers $$$L_{i}$$$ and $$$R_{i}$$$ $$$(1 \leq L_{i} \leq R_{i} \leq n)$$$ – the left and right limit of the range of swords which can kill the $$$i$$$-th monster.

Output

Print the number of swords which are capable of killing all the monsters.

ExamplesInput

4 2
1 2
1 4

Output

2

Input

10 3
1 7
5 10
3 4

Output

0

Note

For the first sample testcase —

• To kill the $$$1$$$-st Monster – $$$1$$$-st or $$$2$$$-nd sword can be used.
• To kill the $$$2$$$-nd Monster – Any of the $$$4$$$ swords can be used.

So, there are $$$2$$$ swords ($$$1$$$-st and $$$2$$$-nd) which are capable of killing both the monsters.

For the second testcase —

• To kill the $$$1$$$-st Monster – Any of $$$1$$$-st, $$$2$$$-nd, $$$3$$$-rd, $$$4$$$-th, $$$5$$$-th, $$$6$$$-th and $$$7$$$-th swords can be used.
• To kill the $$$2$$$-nd Monster – Any of $$$5$$$-th, $$$6$$$-th, $$$7$$$-th, $$$8$$$-th, $$$9$$$-th and $$$10$$$-th swords can be used.
• To kill the $$$3$$$-rd Monster – $$$3$$$-rd or $$$4$$$-th sword can be used.

So, none of the swords are capable of killing all the $$$3$$$ monsters.