Let's throw a party

Let's throw a party

测试数据来自 nnu_contest/1315

Let's throw a party

时间限制:3s

空间限制:64MB

题目描述

期末考试后,班级同学们准备一起聚会。

班级里共有 \(n\) 名同学,第 \(i\) 位同学在期末考试的排名是第 \(i\) 名。

然而,有些同学并不希望聚会中有太多"卷王"。具体来说,每名同学将给出两个正整数\(a_i,b_i\),当且仅当以下条件满足,他才愿意来参加这次聚会:

  • 参加聚会的同学中,成绩不如他的不超过\(a_i\)个
  • 参加聚会的同学中,成绩比他好的不超过\(b_i\)个

这里我们认为,如果一名同学的排名 \(i\) 比另一名同学 \(j\) 低,即\(i<j\),说明他的成绩比另一名同学好。

作为班长,你希望来参加聚会的同学越多越好,请求出这个最大值。

输入格式

第一行一个整数 \(t\) ,表示有 \(t\) 组测试数据。

对于每组数据,第一行包含一个整数\(n\)。

接下来\(n\)行每行两个整数\(a_i\),\(b_i\),含义如题中所述。

输出格式

共 \(t\) 行,每行一个正整数,表示答案。

样例输入1

2
3
1 2
2 1
1 1
2
0 0
0 1

样例输出1

2
1

样例输入2

5
47
20 24
5 35
33 30
20 38
32 44
27 23
37 28
40 46
38 25
24 19
37 21
37 25
11 34
20 9
33 6
3 3
44 40
5 30
14 40
38 0
45 32
21 25
3 10
3 28
38 29
28 12
11 24
16 25
16 26
41 4
42 30
5 0
7 14
35 16
20 32
25 38
43 25
35 33
32 40
27 46
17 43
10 7
38 22
32 23
23 0
46 45
8 42
77
71 18
64 54
6 8
35 28
50 34
18 1
75 36
9 55
18 52
13 64
31 1
34 57
21 46
45 45
39 54
26 31
68 75
50 68
2 29
31 53
12 59
13 37
32 42
49 1
13 28
53 47
62 76
46 36
46 1
55 17
17 30
68 60
51 18
32 64
25 16
43 19
27 68
63 53
30 59
75 60
41 37
0 11
54 6
6 8
68 69
28 46
45 30
74 53
34 70
17 35
66 73
25 34
44 34
70 23
9 30
60 26
2 56
27 14
24 24
65 72
12 15
56 26
6 58
59 61
14 29
42 55
47 24
39 31
76 3
51 0
61 70
13 33
67 49
51 26
73 30
56 14
61 13
80
75 24
53 72
21 41
77 79
49 1
66 79
14 33
20 25
10 18
28 31
68 67
1 20
27 43
9 19
24 22
55 29
42 35
24 55
37 18
32 13
4 47
29 44
6 4
42 66
72 30
9 7
79 29
61 52
3 63
5 0
69 10
77 68
47 8
46 30
0 48
70 29
79 64
71 3
2 79
17 52
23 74
36 43
64 74
19 45
66 45
43 39
33 73
40 20
18 17
23 24
76 67
72 69
35 0
0 62
23 8
12 61
66 27
37 18
48 48
61 6
45 54
22 25
21 10
46 22
13 73
27 5
71 32
26 43
68 29
40 67
72 57
69 38
73 3
59 2
25 60
69 7
10 46
70 63
14 69
20 35
11
5 3
5 9
2 0
1 3
1 6
7 9
3 10
9 5
2 4
8 2
5 5
18
1 6
15 3
10 15
15 8
16 16
2 4
1 16
13 10
10 4
0 2
6 11
1 2
4 0
17 14
8 10
0 9
16 1
7 17

样例输出2

26
39
40
6
9

样例解释

可行的最优方案:

第一组样例中,邀请第一名同学和第二名同学。

第二组样例中,邀请第一名同学。

数据范围及限制

\(1\le t\le 10, 1\le n\le 2*10^5, 0\le a_i,b_i\le n\)

信息

ID
3044
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者