SP9805 BEHAPPY - Be Awesome As Barney Stinson

Barney Stinson ;) is way too flirty. He has many girlfriends and he wants to keep all of them happy. He has **M** girlfriends. He bought **N** gifts for them. Now he knows that some girlfriends need more gifts and some need less. So he decided that he will give atleast **Ai** gifts and at most **Bi** gifts to his **i**th girlfriend. He has to give away all the **N** gifts. Tell us in how many different ways he can do this.

For each test case, first line contains two integers **M** and **N,** then follows M lines each having two integers **Ai** and **Bi** (1

N/A