題目描述

在察覺到這一驚人事實后，大哈魚覺得花光所有理智去購入 m 顆白砂糖塊來爲他的 n 杯水入味。第 i 杯水有著 a_i 個單位的水，由於某些原因，這杯水内已經加入了 s_i 顆白砂糖塊。大哈魚判定一杯水有沒有味取決於他舌頭的靈敏度 p ：若一杯水有著 A 個單位的水並放入了 S 顆白砂糖塊，並有 A <= S * p ，則大哈魚會説這杯白開水是有味的。請你給出大哈魚在分配完白砂糖塊后有味的白開水的最大數量 MAX

輸入格式

n m p

a₁ s₁ 

a₂ s₂ 

...

a_n s_n 

輸出格式

MAX

 

Samples

5 3 2
3 2
6 2
9 4
7 3
11 5

4

提示

1 <= n <= 200000

1 <= m <= 10^15

1 <= p <= 1000

1 <= a_i <= 10^15

1 <= s_i <= 300000

原始資料

• Zero1 題號：b124
• Hydro 題號：Z1124
• Locale：zh_CN
• Display：open