gwcc2p5

G.W. Coding Contest 2 P5: Andy's Lunch Dilemma

It's lunch time at Dr. G.W. Williams, but there's a small issue for Andy. Andy wants to sit around his \(N\) friends, but it seems like all the other tables in the cafeteria are taken except for one line of \(M\) tables numbered from 1 to \(M\). Andy sees his friends sitting at different tables and wants to sit in a spot to minimize the time he has to walk to each friend combined (to travel from one table to another takes 1 second).

Also, Andy has a rating for each of his \(N\) friends, the higher rated a friend is, Andy will walk that many more times faster to the friend. Can you help him find the optimal position?

Note: all test cases are created such that there will only be one optimal answer. Also all times to get to any friend should be a whole number, if the time it takes due to a rating is a decimal then it will take AT LEAST that long to reach that friend.

Input Specification:

The first line of input will contain two integers, \(N\) and \(M\) \( \{1 \leq N, M \leq 2\times10^6\} \), with \(N\) representing the number of friends Andy has, and \(M\) representing the number of tables Andy's friends can sit at.

The next \(N\) lines will contain two integers, \(X\) and \(R\), with \(X\) representing the table on the line of tables friend \(i\) sits at, and \(R\) representing the rating of that friend \(\{1 \leq R \leq 5\times 10^6\}\).

There will at least be 1 friend with rating 1.

Output Specification:

Output one integer, Andy's optimal position on the line of tables.

TIME CONSTRAINT: 1s

Sample Input 1:

4 10
1 1
2 1
4 1
10 5

Sample Output 1:

Explanation for Sample Input 1:

Sitting at table 2 means it takes 1 second to get to friend 1, 0 seconds to get to friend 2, 2 seconds to get to friend 3, and 2 seconds to get to friend 4. Any other position will increase the overall time.