San

컴퓨터 게임 속 주인공이 된 꿈을 꾼 적이 있는가? 이 이야기의 주인공 브라니미르가 지금 그런 꿈을 꾸고 있다.

브라니미르의 꿈속 세계는 왼쪽에서 오른쪽으로 늘어선 고층 빌딩 $N$개로 이루어져 있다. $i$번째 빌딩의 높이는 $H_i$이고, 그 옥상에는 금화 $G_i$개가 놓여 있다.

게임은 빌딩 중 아무 곳에나 뛰어오르며 시작하고, 그 뒤로 여러 번의 이동이 이어진다. 한 번의 이동에서 브라니미르는 지금 서 있는 빌딩보다 오른쪽에 있으면서 높이가 지금 빌딩보다 낮지 않은 빌딩으로 뛸 수 있다. 사이에 있는 빌딩을 건너뛰어도 된다. 올라선 옥상에서는 금화를 모두 가져간다. 이동을 한 번도 하지 않고 게임을 끝낼 수도 있지만, 다음 단계로 넘어가려면 금화를 $K$개 이상 모아야 한다.

다음 단계로 넘어가는 게임 진행 방법이 몇 가지인지 구하라. 한 게임에서는 방문했지만 다른 게임에서는 방문하지 않은 빌딩이 하나라도 있으면 두 게임은 서로 다른 방법이다.

첫째 줄에 정수 $N$과 $K$가 주어진다. ($1 \le N \le 40$, $1 \le K \le 4 \times 10^{10}$)

다음 $N$개 줄 중 $i$번째 줄에 $i$번째 빌딩을 나타내는 정수 $H_i$와 $G_i$가 주어진다. ($1 \le H_i, G_i \le 10^9$)

다음 단계로 넘어가는 게임 진행 방법의 수를 출력한다.

첫 번째 예제에서 다음 단계로 넘어가는 방법은 세 가지다. 방문한 빌딩 번호로 적으면 {1, 2, 3}, {1, 4}, {4}이다.