#P2114. 兑换礼品
兑换礼品
问题说明
小零和小壹是两个爱玩游戏的小孩,他俩平时最擅长的是解谜游戏,可今天遇到了一个有点难的算法问题,希望能得到你的帮助。他们面对的是一个电子装置,正面有 n 个排成一列的按钮,按钮上贴着编号1~n 号的彩色标签,标签的颜色一共有 k 种(颜色可用整数 0~k-1 表示),每个按钮都各自对应着一个可用积分兑换礼品的礼盒,奇怪的是当只有一人按下按钮时,装置没有任何反应,只有两人同时按动两个具有同样标签颜色的按钮时,这两个按钮之间的所有按钮(包括这两个按钮)所对应的礼盒都被激活可以用积分兑换礼品。
小零和小壹的积分加起来共有 p 分,他俩决定用积分兑换一个礼品,希望你帮他们算一算他俩共有多少种选择按钮的方案,保证可以得到一个兑换积分不超过 p 分的礼品。
输入格式
输入数据有 n+1 行。第一行三个整数 n, k, p,每两个整数之间用一个空格隔开,分别表示按钮的个数 n,标签颜色的数目 k 和他俩的积分值 p;
接下来的 n 行,每行两个整数之间用一个空格隔开,第 i+1 行的两个整数分别表示 第 i 号按钮的标签颜色 Ai 和第 i 号按钮对应礼盒的兑换积分要求 Bi。
输出格式
输出数据有一行。一个正整数,表示可选择按钮的方案总数。
5 2 3
0 5
1 3
0 2
1 4
1 5
3
提示
【数据规模与约定】对于 30%的数据,n ≤ 100;
对于 50%的数据,n ≤ 1000;
对于 100%的数据,2 ≤ n ≤ 200000,1 ≤ k≤ 50,0 ≤ p ≤ 100,0 ≤ Ai < k,0 ≤
Bi ≤ 100。
按钮编号 i |
① | ② | ③ | ④ | ⑤ |
标签颜色 Ai |
0 | 1 | 0 | 1 | 1 |
积分要求 Bi |
5 | 3 | 2 | 4 | 5 |
小零和小壹要按同样颜色的按钮,所有可选的方案包括:选按钮①③,②④,②⑤,④⑤,但是若选择按④⑤号按钮的话,④⑤号按钮之间的礼品兑换积分最低需要 4 分 ,而两人只有 3 分,所以不满足要求。因此,只有前 3 种方案可选。