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

题目背景

在星露谷，你准备前往矿洞探险。矿洞门口堆放着若干块矿石，而你的背包容量有限。

题目描述

背包的最大承重为 $C$（单位：kg）。洞口共有 $n$ 块矿石，第 $i$ 块矿石的重量为 $w_i$ kg，价值为 $v_i$ 元。

每块矿石要么整块放入背包，要么不拿，不能分割。背包内所有矿石的总重量不能超过 $C$。

此外，矿洞主人允许你免费额外携带一块"幸运石"：你可以从所有矿石中至多选择一块，将其指定为幸运石。幸运石不计入背包重量，但其价值仍然计入总收益。你也可以放弃该特权。

求在上述规则下能够获得的最大总价值。

输入格式

第一行两个整数 $n, C$。

接下来 $n$ 行，每行两个整数 $w_i, v_i$，分别表示一块矿石的重量和价值。

输出格式

输出一行一个整数，表示能够获得的最大总价值。

样例输入 #1

3 10
6 10
5 8
5 8

样例输出 #1

26

样例说明 #1

将第 $2, 3$ 块矿石放入背包，总重量为 $10$ kg，总价值为 $16$ 元；再将第 $1$ 块矿石指定为幸运石，不占用承重，额外获得 $10$ 元。最终总价值为 $26$ 元。

样例输入 #2

2 5
3 4
3 4

样例输出 #2

8

样例说明 #2

若不使用幸运石，背包最多只能装入一块矿石，价值为 $4$ 元。将其中一块放入背包，另一块指定为幸运石，总价值为 $8$ 元。

提示

【数据范围】

对于全部测试数据，$1 \le n \le 2000$，$1 \le C \le 2000$，$1 \le w_i \le 2000$，$1 \le v_i \le 10000$。

各子任务如下：