The Mad Hatter's hat-searching quest now continues in a new town. In this town, there are ~N~ varieties of hats (numbered from ~1~ to ~N~) being traded at ~M~ stores (numbered from ~1~ to ~M~). The ~i~-th store will sell a hat of type ~h_i~ in exchange for any hat whose type is between ~a_i~ and ~b_i~ (inclusive). The Mad Hatter can perform a trade at the same store more than once.

The Mad Hatter starts with a single hat of type ~1~. What is the maximum possible number of distinct hat types that he can wear at least once?

Constraints

~1 \le N \le 10^5~

~1 \le M \le 10^5~

~1 \le h_i \le N~

~1 \le a_i \le b_i \le N~

Input Specification

The first line contains two space-separated integers ~N~ and ~M~.

~M~ lines follow; the ~i~-th one contains three space-separated integers ~h_i~, ~a_i~, and ~b_i~.

Output Specification

Output a single integer: the maximum number of hat types that can be worn.

Sample Input

5 4
4 1 2
5 1 1
2 4 4
3 4 5

Sample Output

4

Explanation for Sample Output

It is possible to wear hats of type 1, 2, 3, and 4 using the sequence of trades ~1 \to 4 \to 2 \to 4 \to 3~.