Buy Figurines

During the "Hues of the Violet Garden" event, As the professional Lady Guuji hired, Sayu is assigned to buy one of the figurines, that is "Status of Her Excellency, the Almighty Narukami Ogosho, God of Thunder".

There are $n$ people numbered from $1$ to $n$ who intent to buy a figurine and the store has $m$ windows with $m$ queues identified from $1$ to $m$. The $i$-th person has an arrival time $a_i$ and a spent time $s_i$ to buy a figurine(It guaranteed that everyone's arrival time $a_i$ is different). When a person arrives at the store, he will choose the queue with the least number of people to queue. If there are multiple queues with the least number of people, he will choose the queue with the smallest identifier. It should be noted that if someone leaves the queue at the same time, the person will choose the queue after everyone leaves the team.

Sayu has been here since last night so she could buy a figurine. But after waiting and waiting, her eyes started to feel real droopy and... overslept. If Sayu doesn't buy one of these figurines, the Tenryou Commission tengu will lock her up for life! The store will close after these $n$ people buy figurines, that means she must wake up before the last one leaves. Now Lady Guuji wants to know the latest time Sayu wakes up.

For example, there are two people in the same line, $a_1=1, s_1=2, a_2=2, s_2=2$. When the first person arrives, there is no one in the line, so the start time and end time of purchasing the figurine are $1$ and $3$. When the second person arrives, the first person is still in line, so the start time and end time of purchasing the figurine are $3$ and $5$. And if the end time of the last person is $x$, the answer is $x$.

The first line contains one integer $T$ $(1 \le T \le 10)$ .

The first line of each test case contains two positive integers $n$ and $m$ $(1\le n \le 2 \times 10^5,1\le m \le 2 \times 10^5)$ --- the number of people and the number of queues.

Then, $n$ lines follow, each consisting of two integers $a_i$ and $s_i$ $(1\le a_i,s_i \le 10^9)$ --- the arrival time and spent time of $i$-th person.

It guaranteed that the sum of $n$ does not exceed $2 \times 10^6$, and the sum of $m$ does not exceed $2 \times 10^6$.

For each test case:

print a line containing a single integer --- the latest time Sayu wakes up, that means the end time of the last person.

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

7

2022“杭电杯”中国大学生算法设计超级联赛（5）