Election Time

Interview

Time limit1sMemory limit128 MB

Summary

Each cow has first round votes A and second round votes B; the top K by A advance, then the one with the largest B among them wins. Output the winner's index.

Level: Medium4 of 10
Topics: Sorting, Array, Greedy, Implementation
Solved: No attempts yet

Problem

The cows are holding their first presidential election after overthrowing the tyrannical Farmer John, and Bessie is one of $N$ cows ( $1 \le N \le 50000$ ) running for President. Before the election actually takes place, Bessie wants to figure out who has the best chance of winning.

The election is held in two rounds. In the first round, the $K$ cows ( $1 \le K \le N$ ) with the most votes advance to the second round. In the second round, the cow with the most votes becomes President.

Cow $i$ is expected to receive $A_i$ votes ( $1 \le A_i \le 1000000000$ ) in the first round and $B_i$ votes ( $1 \le B_i \le 1000000000$ ) in the second round (if it advances). Determine the index of the cow that is expected to win the election. No two values in the list of $A_i$ are equal, and likewise no two values in the list of $B_i$ are equal.

Input

Line 1: Two space-separated integers $N$ and $K$ .
Lines 2 to $N+1$ : Line $i+1$ contains two space-separated integers $A_i$ and $B_i$ , describing cow $i$ .

Output

Line 1: The index of the cow that is expected to win the election.

Examples1

Example 1
Input
```
5 3
3 10
9 2
5 6
8 4
6 5
```
Expected output
```
5
```