小 X 开了一家糖果店，售卖 n 种糖果，每种糖果均有无限颗。对于不同种类的糖果，小 X 采用了不同的促销策略。具体地，对于第 i (1 \le i \le n) 种糖果，购买第一颗的价格为 x_i 元，第二颗为 y_i 元，第三颗又变回 x_i 元，第四颗则为 y_i 元，以此类推。

小 R 带了 m 元钱买糖果。小 R 不关心糖果的种类，只想到得到数量尽可能多的糖果。你需要帮助小 R 求出，m 元钱能购买的糖果数量的最大值。

输入的第一行包含两个正整数 n, m，代表糖果的种类数和小 R 的钱数。

输入的第 i+1 (1 \le i \le n) 行包含两个正整数 x_i, y_i，分别表示购买第 i 种糖果时第奇数颗的价格和第偶数颗的价格。

输出一行一个非负整数，表示 m 元钱能购买的糖果数量的最大值。

【样例 1 解释】

小 R 可以购买 4 颗第一种糖果，共花费 4 + 1 + 4 + 1 = 10 元。

【样例 2 解释】

小 R 可以购买 1 颗第一种糖果、1 颗第二种糖果与 6 颗第三种糖果，共花费 1 + 2 + 12 = 15 元。

对于所有测试数据，均有：

• 1 \le n \le 10^5；
• 1 \le m \le 10^{18}；
• 对于所有 1 \le i \le n，均有 1 \le x_i, y_i \le 10^9。

::cute-table{tuack}

特殊性质 A：对于所有 1 \le i \le n，均有 x_i = y_i。

特殊性质 B：对于所有 1 \le i \le n，均有 x_i \ge y_i。

NOIP