eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Числова піраміда

Числова піраміда

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

"Кому потрібна ядерна зброя, якщо у Вас є така сила як Інтернет?"

Лія Вакефієлд

На рисунку зображено числову піраміду. Шлях завжди починається на вершині піраміди і завершується внизу. Дозволено переміщуватись лише на сусідні комірки піраміди, розміщені нижче. Вартість шляху дорівнює сумі чисел у комірках на пройденому шляху (включаючи першу та останню).

Знаючи значення всіх чисел у комірках піраміди і деяке число S, підрахуйте кількість шляхів, вартість яких рівна S.

Вхідні дані

Вхідні дані складаються з декількох тестових випадків. Кожен тестовий випадок починається рядком, у якому задано два цілих числа N і S (2N50, 0S < 500), відповідно висота піраміди і задана вартість шляху. Далі йде N рядків, які описують саму числову піраміду. У кожному з цих рядків розміщено відокремлені пропусками числа від 0 до 9. Перший рядок містить одне число, другий - 2, ..., передостанній - N-1, останній - N чисел.

Вхідні дані завершуються рядком, який містить N = S = 0. Цей рядок не опрацьовується. У одному тесті міститься не більше 30 тестових випадків.

Вихідні дані

Для кожного випадку виведіть кількість вказаних шляхів.

Приклад

Вхідні дані #1
6 28
8
8 8
6 5 3
9 5 9 5
6 4 4 1 3
2 6 9 4 3 8
0 0
Вихідні дані #1
1