E2. Космическое путешествие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Умный Бобер из ABBYY планирует совершить космическое путешествие на суперсовременном космическом корабле, за время которого он посетит n планет. Для i-ой планеты известны числа ai — максимальное число чемоданов, которые инопланетному туристу разрешено провезти на планету, и bi — число жителей на планете.

В путешествие Умный Бобер возьмет с собой сувениры из ABBYY. Сувениры упаковываются в чемоданы, по x штук в каждый. На корабль Бобер возьмет ровно a1 + ... + an чемоданов.

Высаживаясь на i-ой планете, Бобер берет с собой ai чемоданов. В первый день пребывания на планете Бобер гуляет и знакомится с жителями. Во второй и все последующие дни Бобер дарит жителям сувениры — каждому из bi жителей по сувениру каждый день. Бобер покидает планету вечером того дня, когда сувениров становится меньше, чем жителей (то есть как только на следующий день он не сможет подарить нужное количество сувениров). Оставшиеся сувениры он оставляет в отеле.

Всего Бобер собирается путешествовать ровно c дней. Время, затраченное на перелеты между планетами, считается равным нулю. Сколькими способами можно выбрать целое положительное число x так, чтобы планируемое путешествие заняло ровно c дней?

Входные данные

Первая строка входных данных содержит целые числа n и c, разделенные пробелом, — число планет, которые Бобер собирается посетить, и число дней, отведенных на путешествие, соответственно.

Следующие n строк содержат пары целых чисел ai, bi (1 ≤ i ≤ n), разделенных пробелом, — число чемоданов, разрешенных для ввоза на i-ю планету, и число жителей на i-ой планете, соответственно.

Ограничения на входные данные для получения 30 баллов:

  • 1 ≤ n ≤ 100
  • 1 ≤ ai ≤ 100
  • 1 ≤ bi ≤ 100
  • 1 ≤ c ≤ 100

Ограничения на входные данные для получения 100 баллов:

  • 1 ≤ n ≤ 104
  • 0 ≤ ai ≤ 109
  • 1 ≤ bi ≤ 109
  • 1 ≤ c ≤ 109

В связи с возможностью переполнения рекомендуется использовать 64-битную арифметику. Возможны варианты решений, в которых переполняется даже 64-битная арифметика. Поэтому будьте аккуратны в вычислениях!

Выходные данные

Выведите единственное целое число k — количество способов выбрать x так, чтобы путешествовать ровно c дней. Если существует бесконечно много вариантов выбора x, выведите -1.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
2 5
1 5
2 4
Выходные данные
1
Примечание

В первом примере существует единственное подходящее значение x = 5. Тогда на первую планету Бобер берет 1 чемодан с 5 сувенирами. Здесь он проводит 2 дня: первый день гуляет, второй день дарит 5 сувениров. На вторую планету он берет 2 чемодана с 10 сувенирами. Здесь он проводит 3 дня — один день гуляет, еще два дня дарит по 4 сувенира и последние 2 сувенира оставляет в отеле. Всего в путешествии бобер проводит 5 дней.

При x = 4 и меньше Бобру не хватит сувениров на второй день на первой планете, и путешествие закончится слишком быстро. При x = 6 и больше Бобер проведет как минимум на один день больше на второй планете, и путешествие затянется.