#P15609. [2026年保加利亚国家队组队赛Junior]Lyutenica辣椒酱

[2026年保加利亚国家队组队赛Junior]Lyutenica辣椒酱

题目背景

萨什卡(Sashka)准备为冬天购买辣椒酱。共有 nn 种不同的辣椒酱,编号为 11nn

这些辣椒酱在两个商店中出售:商店 A 和商店 B。对于每一种辣椒酱,萨什卡最多购买一罐,并且如果购买该种辣椒酱,只能从两个商店中的一个购买。

商店 A 中第 ii 种辣椒酱的价格为 aia_i 列弗,商店 B 中第 ii 种辣椒酱的价格为 bib_i 列弗。

萨什卡在商店 A 的购物预算最多为 xx 列弗,在商店 B 的购物预算最多为 yy 列弗。

她希望购买尽可能多种不同的辣椒酱。请你求出她最多可以买到多少种不同的辣椒酱。

输入格式

第一行包含三个整数 n,x,yn,x,y,分别表示辣椒酱的种类数、商店 A 的预算和商店 B 的预算。

接下来 nn 行,每行包含两个整数 ai,bia_i,b_i,分别表示第 ii 种辣椒酱在商店 A 和商店 B 的价格。

输出格式

输出一个整数,表示萨什卡最多可以买到的不同辣椒酱种类数。

样例 #1

样例输入 #1

3 2 3
2 2
1 3
4 2

样例输出 #1

2

样例解释 #1

萨什卡可以从商店 A 购买第 22 种辣椒酱,花费 11 列弗;从商店 B 购买第 33 种辣椒酱,花费 22 列弗。

这样一共购买了 22 种不同的辣椒酱。

样例 #2

样例输入 #2

5 6 12
5 3
1 5
5 4
6 6
3 7

样例输出 #2

4

数据范围

对于所有测试数据,保证:

1n2000,1\le n\le 2000, 0x,y10000,0\le x,y\le 10000, 0ai,bi10000(1in).0\le a_i,b_i\le 10000\quad (1\le i\le n).

子任务

子任务编号 分值 依赖子任务 额外限制
00 -- 样例测试
11 1111 00 x,y500, n12x,y\le 500,\ n\le 12
22 2424 0,10,1 x,y500, n200x,y\le 500,\ n\le 200
33 99 -- y=0y=0
44 1010 对所有 1i,jn1\le i,j\le n,有 bi=bjb_i=b_j
55 1414 对所有 1in1\le i\le n,有 ai=bia_i=b_i
66 3232 0,1,2,3,4,50,1,2,3,4,5 无额外限制

只有通过某一子任务及其所有依赖子任务的全部测试,才能获得该子任务的分数。