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$.