영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
A board with N members is planning to have a meeting. Due to the large number of board members, it is difficult to find a time that suits everyone, but the aim is to have as many people as possible attend the meeting.
Each member is available during a number of different time intervals, where each time interval [a, b] means that the member can attend if the meeting starts at some time t where a ≤ t ≤ b. Since some members are very careless with their calendars, the same member may accidentally give you overlapping time intervals, e.g., [1, 3] and [2, 4], even though one interval would have sufficed, in this case [1, 4].
Calculate the maximum number of members who can attend the meeting.
Input
The first line contains an integer N (1 ≤ N ≤ 2 · 10^5), the number of members on the board.
This is followed by N lines, one for each board member. The i-th line starts with the number of time intervals m_i (1 ≤ m_i ≤ 2 · 10^5) during which the i-th member can attend. This is followed by m_i pairs of integers, one for each interval. These pairs a, b (0 ≤ a ≤ b ≤ 10^9) represent the interval [a, b].
Let B=∑_{i=1}^N m_i be the sum of the number of time intervals during which all members are available. It is given that B ≤ 2 · 10^5.
Output
Print a single line with an integer – the maximum number of members that can attend the meeting if the start time is chosen optimally.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 10 | B ≤ 100 and 0 ≤ a ≤ b ≤ 100 |
| 2 | 15 | B ≤ 1,000, and 0 ≤ a ≤ b ≤ 4,000, and no single member has two overlapping time intervals |
| 3 | 30 | No single member has two overlapping time intervals |
| 4 | 15 | B ≤ 1,000 and 0 ≤ a ≤ b ≤ 4,000 |
| 5 | 30 | No additional constraints. |
Explanation of Samples
In the first example, we can choose to start the meeting at time 4, when members 2 and 3 can attend. This case could be included in all test case groups.
Examples 2 and 3 could not be included in test case groups 2 or 3.
예제
예제 1
3 2 1 3 5 6 4 1 10 11 12 17 18 14 15 1 4 4
2
예제 2
3 3 2 8 2 7 5 6 4 7 15 15 20 9 13 18 20 3 12 19 9 16 12 16
2
예제 3
3 2 5 14 0 20 3 5 16 5 11 8 9 2 7 11 7 18
3