该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 X 开了一家糖果店，售卖 $n$ 种糖果，每种糖果均有无限颗。对于不同种类的糖果，小 X 采用了不同的促销策略。具体地，对于第 $i$ ($1 ≤ i ≤ n$) 种糖果，购买第一颗的价格为 $x_i$ 元，第二颗为 $y_i$ 元，第三颗又变回 $x_i$ 元，第四颗则为 $y_i$ 元，以此类推。 小 R 带了 $m$ 元钱买糖果。小 R 不关心糖果的种类，只想得到数量尽可能多的糖果。你需要帮助小 R 求出，$m$ 元钱能购买的糖果数量的最大值。

输入格式

从文件 candy.in 中读入数据。 输入的第一行包含两个正整数 $n, m$，代表糖果的种类数和小 R 的钱数。 输入的第 $i + 1$ 行 ($1 ≤ i ≤ n$) 行包含两个正整数 $x_i$, $y_i$，分别表示购买第 $i$ 种糖果时第奇数颗的价格和第偶数颗的价格。

输出格式

输出到文件 candy.out 中。 输出一行一个非负整数，表示 $m$ 元钱能购买的糖果数量的最大值。

样例 1 输入

1 2 10
2 4 1
3 3 3

样例 1 输出

1 4

样例 1 解释

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

样例 2 输入

1 3 15
2 1 7
3 2 3
4 3 1

样例 2 输出

1 8

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

样例 3

见选手目录下的 candy/candy3.in 与 candy/candy3.ans。 该样例满足测试点 $6$ 的约束条件。

样例 4

见选手目录下的 candy/candy4.in 与 candy/candy4.ans。 该样例满足测试点 $8, 9$ 的约束条件。

样例 5

见选手目录下的 candy/candy5.in 与 candy/candy5.ans。 该样例满足测试点 $11, 12$ 的约束条件。

样例 6

见选手目录下的 candy/candy6.in 与 candy/candy6.ans。 该样例满足测试点 $13$ 的约束条件。

样例 7

见选手目录下的 candy/candy7.in 与 candy/candy7.ans。 该样例满足测试点 $17, 18$ 的约束条件。

数据范围

对于所有测试数据，均有： • $1 ≤ n ≤ 10^5$； • $1 ≤ m ≤ 10^{18}$； • 对于所有 $1 ≤ i ≤ n$，均有 $1 ≤ x_i, y_i ≤ 10^9$。

特殊性质 A：对于所有 $1 ≤ i ≤ n$，均有 $x_i = y_i$。 特殊性质 B：对于所有 $1 ≤ i ≤ n$，均有 $x_i ≥ y_i$。