고용

재현이는 초고층 건물 "제2사과타워"를 짓기 위해 노동자를 고용하려고 한다. $1$번부터 $N$번까지 총 $N$명이 지원했으며, $i$번째 노동자는 최저임금 $S_i$와 건설 자격증 레벨 $Q_i$를 가지고 있다. 따라서 $i$번째 노동자를 고용하려면 그에게 $S_i$ 이상의 임금을 지급해야 한다.

정부는 건설 자격증을 장려하기 위해, 고용된 모든 노동자의 임금이 각자의 자격증 레벨에 정비례하도록 하는 규정을 만들었다. 즉, 하나의 실수 계수 $k$를 정하면 고용된 노동자 $i$는 정확히 $Q_i \times k$의 임금을 받는다. 임금은 정수가 아닌 실수여도 된다. 고용한 모든 노동자에 대해 $Q_i \times k \ge S_i$가 성립해야 하므로, 고용한 노동자 전원의 최저임금 조건이 만족되도록 $k$를 충분히 크게 잡아야 한다.

재현이는 $W$달러를 가지고 있다. 자격증 레벨에는 관심이 없고 건물을 최대한 빨리 짓고 싶으므로, 지급하는 임금의 총합이 $W$ 이하가 되도록 하면서 최대한 많은 노동자를 고용하려고 한다. 고용할 수 있는 노동자 수의 최댓값을 구하여라.

표준 입력으로 다음 데이터가 주어진다.

• 첫째 줄에 노동자의 수 $N$과 가진 돈 $W$가 공백으로 구분되어 주어진다.
• 이어지는 $N$개의 줄 중 $i$번째 줄에는 $i$번째 노동자의 최저임금 $S_i$와 자격증 레벨 $Q_i$가 공백으로 구분되어 주어진다.

가진 돈 안에서 고용할 수 있는 노동자 수의 최댓값을 정수 하나로 출력한다.

• $1 \le N \le 500{,}000$ (지원한 노동자의 수)
• $1 \le S_i \le 20{,}000$ (노동자 $i$의 최저임금)
• $1 \le Q_i \le 20{,}000$ (노동자 $i$의 자격증 레벨)
• $1 \le W \le 10{,}000{,}000{,}000$ (사용할 수 있는 돈)
• 입력으로 주어지는 모든 수는 정수이다.