题目描述

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

输入

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

输出

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

输入样例

2 10
4 1
3 3

输出样例

4

提示

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

3 15
1 7
2 3
3 1

8

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。