You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

期末考试结束后，校长希望班主任参考每个人的数学期末成绩（下称考试成绩）和数学选拔成绩（下称选拔成绩）作为参考，并推荐一批优秀的学生，这个整理推荐名单的任务就由班主任负责。校长接受推荐的流程是这样的：

在不考虑选拔成绩的情况下，只考虑考试成绩不低于 $130$ 分的学生； 一共接受 $K$ 批次的推荐名单； 同一批推荐名单上的学生的考试成绩应严格递增； 在同一批推荐名单中，即使有的学生考试成绩与前一个人相同，但其参加过选拔考试，且成绩不小于校长设定的选拔考试成绩，则也可以接受。 给定全体学生的考试成绩和他们的选拔成绩，请你帮班主任算一算，他最多能向校长推荐多少学生？

输入格式：

输入第一行给出 $3$ 个正整数： $N,K,S$

$N$ 代表有 $N$ 个学生

$K$ 代表最多可以推荐 $K$ 批次。

$S$ 代表校长设定的选拔分数的分数线。

随后 $N$ 行，每行给出两个分数，依次为一位学生的期末成绩（最高分 $150$）和选拔成绩（最高分 $100$）。

输出格式：

在一行中输出班主任最多能向校长推荐的学生人数。

样例

input:

10 2 90
145 0
129 91
135 88
135 0
135 90
140 0
140 0
140 95
140 89
150 100

output:

8

样例解释：

第一批可以选择 $135、140、145、150$ 这四个分数的学生各一名，此外额外加入

考试 $135$ 选拔 $90$ 分的学生

考试 $140$ 选拔 $95$ 分的学生

第二批就只剩下 $135$、$140$ 两个分数的学生各一名可以进入名单了。最终一共 $8$ 人进入推荐名单。

限制与约定

对于 $40\%$ 的数据，$1 \le n \le 100$ , $1 \le k \le 100$ 。

对于 $100\%$ 的数据，$N \le 10^5 , k \le 5 \times 10^5 , 1 \le S \le 100 $

• 时间限制: $1 s$
• 空间限制: $256 MB$