← 返回题目列表

AtCoder · code_festival_2015_okinawa_b

B. 小心潮湿!

中文机器翻译题面 查看原题

问题

因此Wolf Sothe很喜欢吃冲绳荞麦面(冲绳的一种著名食品,由面条和汤制成),今天他来到了一家冲绳荞麦面餐厅。有 N 不同种类的冲绳荞麦面。一开始, i_{th} 冲绳荞麦面的种类包括 a_i 克面条和 b_i 克汤。

面条购买后会吸收汤汁。具体来说,对于 i_{th} 一种冲绳荞麦面,如果我们等待的话 t (t 是一个实数,使得 t≧0) 购买后几秒钟,面条的重量将为 min( a_i + t , a_i + b_i ) 克,汤的重量将为 max( b_i − t , 0 ) 克。每种冲绳荞麦面的等待时间都是独立的。

Wolf Sothe会在其中挑选几种冲绳荞麦面 N 种买。每种冲绳荞麦面都只有 1 种。

狼索斯想吃东西 X 或以上 X 克面条和 Y 或以上 Y 汤共克。找到只需要最少数量的冲绳荞麦面的最佳解决方案。

请注意,Wolf Sothe 吃冲绳荞麦面不需要花费时间,因此 Wolf Sothe 在吃东西时不会吸收。换句话说,沃尔夫·索特吃饭时,面条不会吸收汤。


输入

输入将通过以下格式的标准输入给出。

N X Y
a_1 b_1
:
a_N b_N
  • 第一行,整数 N(1≦N≦50), X(1≦X≦10,000), Y(1≦Y≦10,000) 将用空格给出。
  • 从第二行开始有 N 每行附加行 a_i (1≦ a_i ≦10,000), b_i (1≦ b_i ≦10,000) 将用空格给出。

输出

请输出让狼索特吃到的冲绳荞麦面最少需要购买的数量 X 或以上 X 克面条和 Y 或以上 Y 克汤。

如果没有满足Wolf Sothe需求的解,则输出 -1.

在输出末尾打印换行符。


输入示例 1

3 9 7
3 4
8 1
4 5

输出示例 1

2

购买第1种和第3种冲绳荞麦面。第一种冲绳荞麦面请稍等 2 吃饭前第二次。第3种冲绳荞麦面,购买后请尽快食用。这样一来,就可以吃 (3 + 2) + (4 + 0) = 9 克面条和 (4 − 2) + (5 − 0) = 7 克汤。


输入示例 2

5 20 24
8 1
4 6
10 3
10 2
5 10

输出示例 2

-1

因为小于 一共 24 克汤,就算购买了各种冲绳荞麦面,也无法满足沃尔夫·索斯的需要。因此,输出 -1.


输入示例 3

5 6 8
1 3
6 2
2 3
3 5
1 4

输出示例 3

3