6074. T1-[NOIP2025] 糖果店(candy)
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 小 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} | 测试点编号 | $n \le$ | $m \le$ | 特殊性质 | |:----------:|:-------:|:-------:|:--------:| | $1$ | $1$ | $10$ | 无 | | $2,3$ | $2$ | $20$ | ^ | | $4,5$ | $10$ | ^ | ^ | | $6$ | $10^2$ | $10^2$ | A | | $7$ | ^ | ^ | B | | $8,9$ | ^ | ^ | 无 | | $10$ | $10^3$ | $10^4$ | A | | $11,12$ | ^ | ^ | B | | $13$ | ^ | ^ | 无 | | $14$ | $10^5$ | $10^9$ | A | | $15,16$ | ^ | ^ | B | | $17,18$ | ^ | ^ | 无 | | $19,20$ | ^ | $10^{18}$ | ^ | 特殊性质 A：对于所有 $1 \le i \le n$，均有 $x\_i = y\_i$。 特殊性质 B：对于所有 $1 \le i \le n$，均有 $x\_i \ge y\_i$。