Princess's Garden

To celebrate the princess's birthday, the king wants to build a small garden where flowers are in bloom every day from March 1 through November 30.

There are N flowers. Every flower blooms and withers within the same year, and each flower has a fixed blooming date and withering date. If a flower blooms on May 8 and withers on June 13, it is in bloom from May 8 through June 12, and it cannot be seen from June 13 onward.

The number of days in each month this year is as follows.

• April, June, September, November: 30 days
• January, March, May, July, August, October, December: 31 days
• February: 28 days

Choose some of the given flowers so that both conditions below are satisfied.

1. From March 1 through November 30, at least one selected flower must be in bloom every day.
2. The number of selected flowers must be as small as possible.

Find the minimum number of flowers needed.

The first line contains the number of flowers N. (1 <= N <= 100,000)

Each of the next N lines contains the blooming date and withering date of one flower. A date is represented by two integers: month and day. For example, 3 8 7 31 means that the flower blooms on March 8 and withers on July 31.

Print the minimum number of flowers that can be selected so that at least one selected flower is in bloom every day from March 1 through November 30.

If no such selection is possible, print 0.