19110번 - Schedule 다국어

문제

There are $N$ tasks: the $i$-th task has to start at moment $s_i$ and finish at moment $e_i$. There is also a potentially infinite supply of machines. We want to assign tasks to machines. Each task will be assigned to one machine. On the other hand, each machine may handle an arbitrary number of tasks as long as no two of them overlap. Tasks $i$ and $j$ are said to overlap if the intersection of the open intervals $(s_i, e_i)$ and $(s_j, e_j)$ is non-empty.

A machine is turned on at the moment when the earliest of its assigned tasks has to start, and turned off at the moment when the latest of them has to finish. The working time of a machine is the length of the time period between these two moments: we cannot turn a single machine on and off more than once.

Your task is to find the minimum possible number of machines $K$ such that we can use only $K$ machines to perform all tasks. Additionally, when using $K$ machines, find the minimum possible sum of all their working times.

입력

The first line of input contains an integer $T,ドル the number of test cases (1ドル \le T \le 100$).

Each test case begins with a line containing one integer $N$ (0ドル < N \le 10^5$). Each of the next $N$ lines contains two integers $s_i$ and $e_i$ (0ドル \le s_i < e_i \le 10^9$).

It is guaranteed that $N > 50$ for no more than 10 test cases.

출력

For each test case, print two integers in one line: the minimum possible number of machines $K$ to perform all tasks and the minimum sum of all working times when using $K$ machines.

제한

힌트