Building the Wall

EWU Intra University Prog...
Limits 1s, 512 MB

Building walls around a country has become a popular modern day trend. The emperor of Promiseland of very excited with this idea and decides to build walls across the entire border of his country.

For the simplicity, let's assume that Promiseland has only one border with it's neighboring country. Let's also assume that this whole border is just a rectangular area of size 1 * N. The left end of the border is at point (1,1) and the right end of the border is located at point (1,N).

The emperor has made a fortune in real-estate business throughout his lifetime. So he understands the fact that instead of making one wall that covers the entire border, he should build a number of walls, at different locations of the border. He also speculates that not all the border areas are needed to be covered with a wall. As a result, he asks his structural engineers to build M walls for his border.

Each of these walls will cover certain areas across the border. The i'th wall will start at location (1,li) and end at location (1,ri) and will cover all the areas from width li to ri inclusive. But there's a problem. When different engineers were designing these walls, they failed to communicate with each other. As a result, some of the border areas are now being covered by more than one wall.

You now have the detailed design of every wall, you need to write a program that will determine the amount of area that are being covered by more than one wall.

Input

Each of the input files contain a single input.

The input starts with an integer N ( 1 ≤ N ≤ 105 ), the width of the bordering area. The next line will contain an integer M ( 1 ≤ M ≤ 106 ), the number of walls that were designed to cover the border.

Each of the next M lines will contain two integers li and ri ( 1 ≤ li, ri ≤ N ), the description of the i'th wall.

Output

Output a single integer, the total area of the wall that are covered by more than one wall.

Samples

InputOutput
5
2
1 4
2 3
2
InputOutput
5
3
1 2
3 4
5 5
0

Submit

Login to submit.

Statistics

83% Solution Ratio
ewuintra2016.14$6neZAEarliest, Nov '16
MR.Jukerburg11Fastest, 0.1s
fsshakkhorLightest, 524 kB
mdvirusShortest, 267B
Toph uses cookies. By continuing you agree to our Cookie Policy.