题目描述

奶牛们在推翻了专制的Farmer John后迎来了首次选举，贝茜是参与总统竞选的N头奶牛（1 ≤ N ≤ 50,000）之一。不过，在选举正式开始前，贝茜想知道谁最有可能获胜。

选举分为两轮：

1. 第一轮：获得票数最多的K头奶牛（1 ≤ K ≤ N）晋级第二轮。
2. 第二轮：晋级的奶牛中获得票数最多的当选总统。

已知第i头奶牛在第一轮的预期得票数为Ai（1 ≤ Ai ≤ 10^9），若晋级，其在第二轮的预期得票数为Bi（1 ≤ Bi ≤ 10^9）。保证所有Ai互不相同，所有Bi也互不相同。

请确定最终预期当选的奶牛的编号。

输入格式

• 第1行：两个空格分隔的整数N和K
• 第2..N+1行：第i+1行包含两个空格分隔的整数Ai和Bi，表示第i头奶牛的第一轮和第二轮得票数

输出格式

• 第1行：一个整数，表示预期当选的奶牛的编号

输入数据示例1

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

输出数据示例1

5  

数据说明

• 样例解释：
  • 第一轮得票数排序：9（奶牛2）> 8（奶牛4）> 6（奶牛5）> 5（奶牛3）> 3（奶牛1），前3名晋级的是奶牛2、4、5。
  • 第二轮中，晋级奶牛的Bi分别为2（奶牛2）、4（奶牛4）、5（奶牛5），其中奶牛5的Bi最大，故编号5当选。

解题思路

1. 筛选晋级奶牛：
   • 按第一轮得票数Ai从高到低排序，取前K头奶牛进入第二轮。
2. 确定第二轮胜者：
   • 在晋级的奶牛中，按第二轮得票数Bi从高到低排序，取第一名的奶牛编号。

关键点：需注意奶牛的原始编号（输入顺序），排序时需保留编号信息。

算法步骤

1. 读取所有奶牛的Ai、Bi和原始编号。
2. 按Ai降序排序，筛选出前K头奶牛。
3. 在筛选出的奶牛中，按Bi降序排序，取第一个奶牛的编号作为结果。