19440번 - It's All In The Mind 다국어

문제

Professor Zhang has a number sequence $a_1, a_2, \ldots, a_n$. However, the sequence is not complete and some elements are missing. Fortunately, Professor Zhang remembers some attributes of the sequence:

• For every $i \in \{1, 2, \ldots, n\},ドル 0ドル \le a_i \le 100$.
• The sequence is non-increasing: $a_1 \ge a_2 \ge \ldots \ge a_n$.
• The sum of all elements in the sequence is not zero.

Professor Zhang wants to know the maximum value of $\frac{a_1 + a_2}{\sum_{i = 1}^{n}{a_i}}$ among all the possible sequences.

입력

There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ (2ドル \le n \le 100,ドル 0ドル \le m \le n$): the length of the sequence and the number of known elements.

Each of the next $m$ lines contains two integers $x_i$ and $y_i$ (1ドル \le x_i \le n,ドル 0ドル \le y_i \le 100,ドル $x_i < x_{i + 1},ドル $y_i \ge y_{i + 1}$) indicating that $a_{x_i} = y_i$.

There are at most 2000ドル$ test cases, and the total size of the input is no more than 350ドル$ kibibytes.

출력

For each test case, output the answer as an irreducible fraction $p$/$q$ where $p$ and $q$ are integers, and $q > 0$.

제한

힌트