Masala #TWB713QFDS

Ushbu masalada oson va qiyin darajaning farqi N ning chegarasida, Qiyin holati uchun \(N \le 40\)

Hech o'zingizni kompyuter o'yinidagi bosh qahramon sifatida tush ko'rganmisiz? Ushbu hikoyaning qahramoni Alisher hozir aynan shunday tushni ko'rmoqda.

Alisherning tushidagi olam chapdan o'ngga ketma-ket joylashgan N ta osmono'par binolardan iborat. Har bir binoning balandligi \(H_i\)​ va tomida \(G_i\)​ oltin tangalar soni bor.

O'yin Alisherning istalgan binoga sakrashi bilan boshlanadi va bir nechta qadamdan iborat bo'ladi. Har bir qadamda Alisher o'zi turgan binodan o'ng tomonga (bir yoki bir nechta binolarni sakrab o'tib) undan baland yoki teng balandlikdagi binoga sakrashi mumkin. Har safar u binoga chiqqanda, u tomdagi barcha oltin tangalarni yig'adi.

Alisher o'yinni istalgan vaqtda to'xtatishi mumkin, ammo keyingi bosqichga o'tish uchun u kamida K tanga yig'ishi kerak.

Alisherga o'yinni o'tkazishning nechta turli yo'li borligini aniqlashda yordam bering. Agar biror binoni bir o'yinda tashrif qilgan bo'lsa, ikkinchisida tashrif qilmagan bo'lsa, ikkita o'yin bir-biridan farq qiladi

Birinchi qatorda N va K musbat butun sonlari beriladi. Keyingi N qatorda har biri ikkita musbat butun son \(H_i\)​ (binoning balandligi) va \(G_i\)​ (tomdagi oltin tangalar soni) kiritiladi.

\(1 \le N \le 40\)

\(1 \le K \le 4 \times 10^{10}\)

\(1 \le H_i, G_i \le 10^9\)

Alisher o'yinni turli yo'llar bilan o'tkazishi mumkin bo'lgan usullar sonini chop eting.