CSES - Aalto Competitive Programming 2024 - wk1 - Mon - Traffic jam
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Maija is a freshly graduated infrastructure architect and has now been given her first job by the local government: to fix the traffic problems of junction 1337.

Before she can start planning any solutions she needs to understand the nature of the problem. To do this, she starts to analyze the weekly traffic data.

From the records she extracts the following information for n anonymous cars numbered 1,2,\dots,n: Car number i enters the junction some time during the interval [l_i, r_i]. Now she is going to calculate the maximum possible number of cars trying to enter the junction all at once.

Input

The first line contains an integer n which is the number of cars.

The next i^{th} line contain two integers l_i and r_i.

Output

Output the maximum number of cars trying to enter the junction all at once.

Constraints

  • 1 \leq n \leq 10^5
  • 1 \leq l_i \leq r_i \leq 60 \times 60 \times 24 \times 7 = 604800

Example 1

Input:

3
1 4
4 5
4 6

Output:

3

Explanation:

All three cars might arrive to the intersection at second 4

Example 2

Input:

4
1 2
3 5
4 6
7 8

Output:

2

Explanation:

Both cars 2 and 3 might arrive at the intersection at seconds 4 or 5

Example 3

Input:

3
1 604800
54332 421232
32323 44444

Output:

2