Description

花农Hady的花场里有一排整齐的鲜花等着售卖，花农的售卖规则很奇怪，一次只能售卖连续排放的鲜花，有个客户的要求也奇奇怪怪，在给定的价格范围内要买到所有颜色的鲜花，并且数量尽量多，Hady很坚持自己的原则，但又想尽量满足客户的要求，所以找到了学习编程的你，让你帮忙计算该客户最多能买多少盆花？

Input Format

第一行输入花农Hady的鲜花数量n和客户给定的价格k，鲜花的颜色种类数量m
接下来n行数据，每行两个数字分别表示第i盆鲜花的颜色和价格

Output Format

输出一个数字表示客户最多能买到的鲜花数量，如果一盆都买不到的话则输出0.

10 100 3
2 10
1 15
1 10 
2 20
1 30
2 20
2 50
2 10
3 70
1 20

3

Hint

对于30% 的数据 N<=2000；

对于100%的数据 N<=1000000 ，M<=2000 ，k<=10^9 

Source

算法