冷知识

各位做题前可以看看难度（

题目背景

现在是 2018 年，舞萌 FiNALE 终于更新了！

@Orange想要去玩新的曲包——PΛNDθRΛ BΘXXX，而这个曲包里的很多曲子她都很喜欢。曲子都有一个需要消耗的耐力和能获取的 Rating 值，而@Orange她有一个耐力限制，就是说她不能玩太多太难的曲子，不然她就会很累。但是@Orange她又想要去涨 Rating 值。接下来你要帮助@Orange写个歌单，让@Orange在不累的情况下，如何选择歌曲才能让她涨的 Rating 值最大化。

问题描述

给定@Orange的耐力 $W$，以及 $N$ 首歌曲，每首歌曲有一个需要消耗的耐力 $w[i]$ 和一个 Rating 值 $v[i]$。你需要选择一部分歌曲放入歌单，使得这些歌曲的总耐力消耗不超过@Orange的耐力 $W$，且它们的 Rating 值最大。

输入格式

• 第一行：两个整数 $N$ 和 $W$。

  • $N$ 是歌曲数量。
  • $W$ 是@Orange的耐力。

• 接下来的 $N$ 行：每行包含两个整数，表示第 $i$ 首歌曲需要消耗的耐力 $w[i]$ 和 Rating 值 $v[i]$。

输出格式

输出一个整数，表示在不超过@Orange耐力 $W$ 的情况下，能获得的最大总 Rating。

样例输入

4 8
2 3
3 4
4 5
5 8

样例输出

12

解释

• 歌曲 1 消耗耐力 2，Rating 值是 3。
• 歌曲 2 消耗耐力 3，Rating 值是 4。
• 歌曲 3 消耗耐力 4，Rating 值是 5。
• 歌曲 4 消耗耐力 5，Rating 值是 8。

在耐力为 8 的情况下，选择歌曲 2（消耗耐力 3，Rating 4）和歌曲 3（消耗耐力 4，Rating 值 5），总消耗耐力为 7，且总 Rating 值为 9。

数据范围与约定

对于 30% 的数据，$1 \leq N,W \leq 10$

对于 50% 的数据，$1 \leq N,W \leq 10^2$

对于 100% 的数据，$1 \leq N,W \leq 10^3$