15817번 - 배수 공사

영만이네 집은 너무 오래되어서 변기에 물이 줄줄 샌다. 보다 못한 영만이는 마침 집에 파이프가 남아 있어서 직접 배수 공사를 하려고 한다.

하지만 파이프를 자르는 비용이 너무나 비싸기 때문에, 가난한 영만이는 남은 파이프들을 적절히 모아서 원하는 길이로 만들어야 한다. 

영만이가 가지고 있는 파이프의 길이와 그 수량을 알고 있을 때, 파이프를 적당히 합쳐서 x만큼의 길이를 만드는 방법의 수를 구하시오. 파이프를 합치는 순서는 고려하지 않는다.

영만이가 가지고 있는 파이프의 종류의 수 N과 만들고 싶은 합친 파이프의 길이 x가 주어진다. (1 ≤ N ≤ 100 이며, 1 ≤ x ≤ 10 000 이다.)

다음 N개의 줄에 걸쳐서 파이프의 길이 L_i 와 수량 C_i 이 공백을 사이에 두고 주어진다. 길이가 짧은 것부터 순서대로 입력되며, 0 < L_i ≤ x, 0 < C_i ≤ 100 이다. 또한, 입력되는 파이프의 길이는 서로 다르다.

합친 파이프의 길이 x를 만들 수 있는 방법의 수를 출력한다. 방법의 수가 2,147,483,647를 넘는 경우는 없다.