409809: GYM103785 D Elder Ning
Description
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.
InputThe 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.
OutputPrint the number of swords which are capable of killing all the monsters.
ExamplesInput4 2 1 2 1 4Output
2Input
10 3 1 7 5 10 3 4Output
0Note
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.
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.