It's All In The Mind

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

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

1. For every $i \in \{1,2,...,n\}$, $0 \le a_i \le 100$.
2. The sequence is non-increasing, i.e. $a_1 \ge a_2 \ge ... \ge a_n$.
3. 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.

Input

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

In the next $m$ lines, each 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$.

Output

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

Sample Input

2 2 0 3 1 3 1

Sample Output

1/1 200/201

Hint

wange2014

Source

2016 Multi-University Training Contest 2

提交代码