Осада

На замок славного сэра Петрейна напали $n$ вражеских армий. Верные люди доблестного сэра, не жалея себя, добыли планы нападений каждой из армий. Оказалось, что $i$-ая армия собирается напасть первый раз в $a_i$-ый день, а затем нападать на замок каждые $b_i$ дней. Таким образом $i$-ая вражеская армия будет совершать нападения в дни с номерами $a_i$, $a_i + b_i$, $a_i + 2 \cdot b_i$, $\dots$, $a_i + j \cdot b_i$ и т.д.

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

Сэр Петрейн занят продумыванием своего, несомненно, гениального военного плана, поэтому он попросил Вас узнать, в какой день защита замка падет под натиском врагов, то есть в какой день произойдет $k + 1$-ая атака на стены замка доблестного сэра.

В первой строке входного файла заданы два славных целых числа $n$ и $k$ ($1 \le n \le 15$; $0 \le k \le 10^{9}$). В следующих $n$ строках идут описания планов вражеских армий, кровожадно напавших на замок доблестного Сэра. Каждое описание состоит из двух ненавистных целых чисел $a_i$ и $b_i$, разделенных благородным пробелом ($0 \le a_i \le 10^9$; $1 \le b_i \le 10^9$).

В выходной файл выведите единственное число --- номер дня, в который состоится $k + 1$-ая атака вражеских войск на прекрасный замок славного сэра Петрейна и в который доблестные войска благородного сэра падут. Звезды предсказали сэру Петрейну, что ответ не превысит $2 \cdot 10^{18}$.