#P11013. [2016杭电多校]It's All In The Mind

    ID: 10155 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 3 上传者: 标签>CF1200普及-支配关系序列构造欧几里得算法

[2016杭电多校]It's All In The Mind

It's All In The Mind

Problem Description

Professor Zhang has a number sequence a1,a2,...,ana_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∈{1,2,...,n}i \in \{1,2,...,n\}, 0≤ai≤1000 \le a_i \le 100.
  2. The sequence is non-increasing, i.e. a1≥a2≥...≥ana_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 a1+a2∑i=1nai\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 TT, indicating the number of test cases. For each test case: The first contains two integers nn and mm (2≤n≤100,0≤m≤n)(2 \le n \le 100, 0 \le m \le n) -- the length of the sequence and the number of known elements. In the next mm lines, each contains two integers xix_i and yiy_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 axi=yia_{x_i} = y_i.

Output

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

Sample Input

2
2 0
3 1
3 1

Sample Output

1/1
200/201

Author

zimpha

Source

2016 Multi-University Training Contest 2