千宸和栩逸是两个爱玩游戏的小屁孩，他俩平时最擅长的是解谜游戏，可今天遇到了一个有点难的算法问题，希望能得到你的帮助。

他们面对的是一个电子装置，正面有n个排成一列的按钮，按钮上贴着编号1~n号的彩色标签，标签的颜色一共有k种（颜色可用整数0~k-1表示），每个按钮都各自对应着一个可用积分兑换礼品的盒子，奇怪的是当只有一人按下按钮时装置没有任何反应，只有两人同时按动两个具有同样标签颜色的按钮时，这两个按钮之间的所有按钮（包括这两个按钮）所对应的礼盒都被激活可以用积分兑换礼品。

千宸和栩逸的积分加起来有p分，他俩决定用积分兑换一个礼品，希望你帮他们算一算他俩共有多少种选择按钮的方案，保证可以得到一个兑换分不超过p分的礼品。

输入数据有n+1行。

第一行三个整数n，p，k，每两个整数之间用一个空格隔开，分别表示按钮的个数n，标签颜色的数目k和他俩的积分值P；

接下来的n行，每行两个整数之间用一个空格隔开，第i+1行的两个整数分别表示第i号按钮的标签颜色Ai和第i号按钮对应礼盒的兑换积分要求Bi。

输出数据有一行。

一个整数，表示可选择按钮的方案总数。