2022. Election Time

单点时限: 2.0 sec

内存限制: 256 MB

The cows are having their first election after overthrowing the tyrannical Farmer John, and Bessie is one of $N$ cows $(1 \leq N \leq 50,000)$ running for President. Before the election actually happens,however, Bessie wants to determine who has the best chance of winning.

The election consists of two rounds. In the first round, the $K$ cows $(1 \leq K \leq N)$ cows with the most votes advance to the second round. In the second round, the cow with the most votes becomes President.

Given that cow i expects to get $A_i$ votes $(1 \leq A_i \leq 1,000,000,000)$ in the first round and $B_i$ votes $(1 \leq B_i \leq 1,000,000,000)$ in the second round (if he or she makes it), determine which cow is expected to win the election. Happily for you, no vote count appears twice in the $A_i$ list; likewise, no vote count appears twice in the $B_i$ list.

输入格式

  • Line $1$: Two space-separated integers: $N$ and $K$

  • Lines $2 \ldots N+1$: Line $i+1$ contains two space-separated integers: $A_i$ and $B_i$

输出格式

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

样例

Input
5 3
3 10
9 2
5 6
8 4
6 5
Output
5

提示

For the example:

There are 5 cows, 3 of which will advance to the second round. The cows expect to get 3, 9, 5, 8, and 6 votes, respectively, in the first round and 10, 2, 6, 4, and 5 votes, respectively, in the second.

Cows 2, 4, and 5 advance to the second round; cow 5 gets 5 votes in the second round, winning the election.

65 人解决,85 人已尝试。

80 份提交通过,共有 156 份提交。

3.4 EMB 奖励。

创建: 14 年,4 月前.

修改: 4 年,3 月前.

最后提交: 2 月前.

来源: USACO

题目标签