Best Hat in Town II

View as PDF

Submit solution

Points: 25
Time limit: 1.0s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

Input Format

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 Format

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.


There are no comments at the moment.