Princess's Garden

Time limit1sMemory limit192 MB

Summary
Select the minimum number of intervals (flower bloom ranges) to cover every day from March 1 to November 30, or report 0 if impossible.
Level

Medium6 of 10

Topics
Greedy, Intervals, Sorting
Solved
No attempts yet

Problem

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.

Input

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.

Output

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.

Examples2

  1. Example 1

    Input
    4
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10
    Expected output
    2

  2. Example 2

    Input
    10
2 15 3 23
4 12 6 5
5 2 5 31
9 14 12 24
6 15 9 3
6 3 6 15
2 28 4 25
6 15 9 27
10 5 12 31
7 14 9 1
    Expected output
    5