← 返回题目列表

Codeforces · 166/A

A. 排名列表

中文机器翻译题面 查看原题

又一场编程大赛结束了。您拿到了比赛的最终成绩表。该表有以下数据。对于每支球队,我们都会看到两个数字:问题数量和总罚时。然而,我们没有看到任何球队的最终位置。

您非常了解比较两个给定团队的结果的规则。假设a队用总罚时ta解决了pa问题,b队用总罚时tb解决了pb问题。如果a队在比赛中解决了更多的问题,或者解决了相同数量的问题但总时间更少,那么a队最终会比b队获得更高的名次。换句话说,如果 pa > pb,或者 pa = pb 且 ta < tb,则 a 队在最终成绩表中的排名高于 b 队。

认为以相同罚时解决相同题数的队伍共享所有相应名额。更正式地说,假设有一组 x 队在相同的惩罚时间内解决了相同数量的问题。我们还假设 y 队的表现比该组中的球队更好。在这种情况下,该组中的所有团队共享位置 y + 1、y + 2、...、y + x。表现比该组中的团队差的团队从第 y + x + 1 位开始在结果表中获得位置。

你的任务是计算给定列表中共有多少支球队共享第 k 个位置。

输入

第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 50)。然后n行包含球队的描述:第i行包含两个整数pi和ti(1≤pi,ti≤50)——相应地,解决问题的数量和第i队的总惩罚时间。行中的所有数字均以空格分隔。

输出

在唯一的一行中打印出在最终成绩表中获得第 k 名的球队的数量。

示例

输入 #1

7 2
4 10
4 10
4 10
3 20
2 1
2 1
1 10

输出 #1

3

输入 #2

5 4
3 1
3 1
5 3
3 1
3 1

输出 #2

4

注意

第一个样本的最终结果表为:

- 1-3 名 — 解决 4 个问题,惩罚时间等于 10
- 第 4 位 - 解决了 3 个问题,惩罚时间等于 20
- 5-6 位 — 解决 2 个问题,惩罚时间等于 1
- 7 位 — 解决了 1 个问题,惩罚时间等于 10

该表显示,第二名由在罚时 10 时间内解决 4 道题的球队并列。这样的球队共有 3 支。

第二个样本的最终表是:

- 1 位 - 解决 5 个问题,惩罚时间等于 3
- 2-5名 — 解决了3个问题,惩罚时间等于1

该表显示,第四名由在罚时 1 中解决 3 个问题的球队并列。这样的球队有 4 支。