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?
~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~.
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 a single integer: the maximum number of hat types that can be worn.
Sample Input 1
5 4 4 1 2 5 1 1 2 4 4 3 4 5
Output for Sample Input 1
Explanation for Sample Input 1
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~.