30701번 - 돌아온 똥게임

문제

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

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

근호는 매번 아직 돌파하지 않은 방 중 어떤 방에 먼저 들어갈지 자유롭게 정할 수 있으며, 들어간 방에 있는 내용물에 따라 다음과 같이 행동한다.

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

방에 있는 몬스터를 쓰러뜨리거나 장비를 얻을 경우 해당 방을 돌파한 것이며, 근호가 모든 방을 돌파하거나 몬스터에게 패배했을 경우 게임이 끝난다.

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

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

입력

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

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

출력

첫 번째 줄에 근호가 최대로 돌파할 수 있는 방의 수를 출력한다.

제한

노트

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