405597: GYM102006 J Clarifications

Based on a true story.

If you've ever hosted a contest online before, you would know that there are many generic types of clarifications sent from users. Clarifications like "what is the answer for this test case" and "please help, my rating will be ruined" are far too common. Assume there are k types of clarifications.

Hasan is hosting his first contest and it will last for m minutes. Him and the contest administrator, KAN, will be answering clarifications. Hasan decided to answer clarifications of a type only after KAN answers at least one of that type, since he wasn't sure how to handle each type of the clarifications.

Answering a clarification takes one minute. Also, each of KAN and Hasan can answer at most one clarification in one minute. If KAN answered the first clarification of some type at minute x, Hasan will answer clarifications of that type only in minute x + 1 or later. If the first clarification of a type was sent in minute y, it can be answered by KAN in the same minute y. There are no other restrictions, clarifications can be answered in any order.

Throughout the contest, n clarifications were sent. You will be given the time, in minutes, each clarification was sent and its type.

Find the earliest time KAN and Hasan can finish answering all the clarifications if they collaborated in a way that minimizes this time. Note that this time can be after the end of the contest.

The first line of input contains a single integer T (1 ≤ T ≤ 256), the number of test cases.

The first line of each test case contains three space-separated integers m, n, and k (1 ≤ m ≤ 10⁵), (1 ≤ k ≤ n ≤ 10⁵), the duration of the contest, the number of clarifications, and the number of types of clarifications respectively.

Each of the following n lines contains two space-separated integers t_i and p_i (1 ≤ t_i ≤ m, 1 ≤ p_i ≤ k), the time of the i^th clarification and its type, respectively. The clarifications are given in arbitrary order.

It is guaranteed that each of the k types will appear at least once in input.

The total sum of each of m and n over all test cases doesn't exceed 3 × 10⁶.

For each test case, output a single line with the earliest time KAN and Hasan can finish answering clarifications.

2
2 3 2
1 2
2 2
1 1
1 4 1
1 1
1 1
1 1
1 1

2
3