New Year's '19 P8 - Best Hat in Town II

View as PDF

Submit solution

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

Authors:
Problem types

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 hi in exchange for any hat whose type is between ai and bi (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

1N105

1M105

1hiN

1aibiN

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 hi, ai, and bi.

Output Specification

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

Sample Input

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

Sample Output

Copy
4

Explanation for Sample Output

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


Comments

There are no comments at the moment.