## LCC '21 Contest 5 J4 - Fred's Fish

View as PDF

Points: 5 (partial)
Time limit: 3.0s
Memory limit: 64M

Author:
Problem type

Fred has gone fishing at a local park which contains pools of fish, numbered to . There are also fish in the park, the -th fish being in pool with a weight of . It is guaranteed that each fish will have a unique weight.

According to the park's rules, Fred can only fish at one pool and can only take home one fish. Fred also fishes at a rate of fish per hour. He would like to choose one pool to fish, where he would like to take home the heaviest fish in that pool.

Since the heaviest fish is rare, Fred can only fish it up once all other fishes are taken out of the pool. However, he would like the value of the ratio of the weight of the fish he takes to the amount of time he took to fish it to be high.

Given that Fred wants to take home the heaviest fish in the pool he chooses, can you output pool he should choose to fish in to take home the fish with the highest weight to time taken ratio?

#### Input Specification

The first line will contain two space-separated integers, and , the number of pools of fish and number of fish in the park, respectfully.

The next lines will contain space-separated integers, and , the pool the -th fish is in and the weight of the -th fish.

#### Output Specification

Output a single integer, the pool Fred should fish in. If multiple pools have the same weight to time taken ratio, output the one with the smaller index.

#### Sample Input

3 10
1 1
2 5
1 2
3 6
3 4
2 3
1 10
3 7
2 11
1 13

#### Sample Output

2

#### Explanation for Sample

Pool will have fishes of weights , , , and , with a weight to time taken ratio of to . Pool will have fishes of weights , , , with a weight to time taken ratio of to . Pool will have fishes of weights , , , with a weight to time taken ratio of to . Thus, pool has the best ratio.