돌아온 똥게임

유튜브에서 똥게임 광고를 지나치게 많이 본 근호는 직접 똥게임을 설치해서 해 보기로 했다.

근호의 처음 전투력은 $D$이다. 근호 앞에는 $N$개의 방이 있다. 각 방에는 몬스터 또는 장비가 있으며, $i$번째 방($1\leq i\leq N$)에 있는 몬스터 또는 장비의 전투력은 $X_i$이다.

근호는 매번 아직 돌파하지 않은 방 중에서 다음에 들어갈 방을 자유롭게 고를 수 있다. 들어간 방의 내용물에 따라 다음과 같이 행동한다.

• 몬스터가 있는 경우: 근호의 전투력이 몬스터의 전투력보다 크면 몬스터를 쓰러뜨릴 수 있으며, 이후 근호의 전투력에 몬스터의 전투력이 더해진다. 근호의 전투력이 몬스터의 전투력보다 작거나 같으면 근호는 패배한다.
• 장비가 있는 경우: 근호의 현재 전투력과 상관없이 얻을 수 있으며, 근호의 전투력에 장비의 전투력이 곱해진다. 단, 얻고자 하는 장비보다 전투력이 작은 모든 장비를 먼저 얻어야만 그 장비를 얻을 수 있다.

방에 있는 몬스터를 쓰러뜨리거나 장비를 얻으면 그 방을 돌파한 것이다. 근호가 모든 방을 돌파하거나 몬스터에게 패배하면 게임이 끝난다.

근호가 최선의 전략으로 게임을 진행할 때, 돌파할 수 있는 방의 수의 최댓값을 구하여라.

근호가 행동을 통해 올릴 수 있는 전투력에는 상한이 없음에 유의하라.

첫 번째 줄에는 방의 수 $N$과 근호의 시작 전투력 $D$가 공백으로 구분되어 정수로 주어진다. ($1\leq N\leq 100000$, $1\leq D\leq 10^9$)

다음 $N$개 줄에는 한 줄에 방의 정보 $A_i$, $X_i$가 공백으로 구분되어 주어진다. $A_i$는 몬스터가 있는 방이면 1, 장비가 있는 방이면 2이다. $X_i$ ($2\leq X_i\leq 10^9$)는 해당 방에 있는 몬스터 또는 장비의 전투력이다.

첫 번째 줄에 근호가 돌파할 수 있는 방의 수의 최댓값을 출력한다.

근호는 아직도 이 똥게임을 클리어하지 못하고 있다...