You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

糖果店

题目描述

小 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

输入 #1

2 10
4 1
3 3

输出 #1

4

输入输出样例 #2

输入 #2

3 15
1 7
2 3
3 1

输出 #2

8

说明/提示

【样例 1 解释】

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

【样例 2 解释】

小 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 \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$。