У Степана багато подруг, і він хоче, щоб усі вони були щасливими. У нього є \(M\) подруг. Він купив для них \(N\) подарунків. Тепер він знає, що деяким подругам потрібно більше подарунків, а іншим менше. Тому він вирішив, що подарує щонайменше \(A_i\) подарунків і максимум \(B_i\) подарунків для \(i\)-ї дівчини. Він повинен віддати всі \(N\) подарунки.

Знайдіть скількома різними способами він може це зробити.

Формат вхідних даних

Для кожного тесту перший рядок містить два цілих числа \(M\) (\(1 \le M \le 20\)) і \(N\) (\(1 \le N \le 100\)), потім слідує \(M\) рядків, кожен з яких має по два цілих числа \(A_i\) і \(B_i\) (\(1 \le i \le M\), \(0 \le A_i, B_i \le 100\)).

Вхідні дані закінчуються на 0 0.

Формат вихідних даних

Для кожного тесту в окремому рядку введіть кількість різних способів, якими Степан може розподілити подарунки.

Примітка

До прикладу 1:

Він може роздати 5 подарунків своїм 3 подругам 6 різними способами (0 1 4), (0 2 3), (0 3 2), (1 1 3), (1 2 2), (1 3 1) .

Приклад вхідних даних

3 5
0 1
1 3
1 4
0 0

Приклад вихідних даних

6