The Mad Hatter's hat-searching quest now continues in a new town. In this town, there are varieties of hats (numbered from to ) being traded at stores (numbered from to ). The -th store will sell a hat of type in exchange for any hat whose type is between and (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 . What is the maximum possible number of distinct hat types that he can wear at least once?
The first line contains two space-separated integers and .
lines follow; the -th one contains three space-separated integers , , and .
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 .