A Fistful of Dollars

Time limit1sMemory limit128 MB

Summary

Given transaction totals for s people, find the person whose spending exceeds twice that of every other person, or report none.

Level: Easy3 of 10
Topics: Implementation, Array, Brute force
Solved: No attempts yet

Problem

Frequently, when people harm each other, money is a primary motive. As a result, one can often identify suspects by sudden extravagant spending. That is why the police like to have access to financial transaction records.

In this problem, you are to analyze a sequence of financial transactions and find out whether one suspect stands out by spending extravagantly. You are given the recent purchases made by a number of people. A person is a suspect if his recent purchases add up to more than twice those of every other person in that period. You must output which suspect, if any, stands out.

Recall the final lines from the film Fargo: "So that was Mrs. Lundegaard on the floor in there. And I guess that was your accomplice in the wood chipper. And those three people in Brainerd. And for what? For a little bit of money. There's more to life than a little money, you know. Don't you know that? And here ya are, and it's a beautiful day. Well, I just don't understand it." A reminder that money is so often the motive.

Input

The first line contains the number $K$ of input data sets, followed by the $K$ data sets, each of the following form.

The first line of a data set contains two integers $s$ and $t$ : the number of suspects $2 \le s \le 50$ and the number of financial transactions $1 \le t \le 1000$ .

This is followed by $t$ lines, each containing two positive integers $s_i$ and $p_i$ . $s_i$ is the number of the person who made transaction $i$ ( $1 \le s_i \le s$ ), and $p_i$ is the amount of money the transaction was for.

Output

For each data set, output Data Set x: on a line by itself, where $x$ is its number. On the next line, output the number of the suspect who spent more than twice as much as every other suspect in the data set. If there is no such suspect, output No suspect. instead.

Separate two consecutive data sets with a single blank line.

Examples4

Example 1

Input

Expected output

Data Set 1:
No suspect.

Data Set 2:
1

Example 2
Input
```
1
2 2
1 10
2 3
```
Expected output
```
Data Set 1:
1
```
Example 3
Input
```
1
2 2
1 6
2 3
```
Expected output
```
Data Set 1:
No suspect.
```
Example 4
Input
```
1
3 1
1 5
```
Expected output
```
Data Set 1:
1
```