LCC '21 Contest 5 J4 - Fred's Fish

View as PDF

Submit solution

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

Problem type

Fred has gone fishing at a local park which contains N pools of fish, numbered 1 to N. There are also M fish in the park, the i-th fish being in pool p_i with a weight of w_i. 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 1 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, N (1 \leq N \leq 10^5) and M (1 \leq M \leq 10^5), the number of pools of fish and number of fish in the park, respectfully.

The next M lines will contain 2 space-separated integers, p_i (1 \leq p_i \leq N) and w_i (1 \leq v_i \leq 10^5), the pool the i-th fish is in and the weight of the i-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


Explanation for Sample

Pool 1 will have fishes of weights 1, 2, 10, and 13, with a weight to time taken ratio of 13 to 4. Pool 2 will have fishes of weights 3, 5, 11, with a weight to time taken ratio of 11 to 3. Pool 3 will have fishes of weights 4, 6, 7, with a weight to time taken ratio of 7 to 3. Thus, pool 2 has the best ratio.


There are no comments at the moment.