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?
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 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.
3 10 1 1 2 5 1 2 3 6 3 4 2 3 1 10 3 7 2 11 1 13
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.