题目描述

越越存了一笔巨款准备开一家公司，现在他正准备招聘他的第一批员工。

现在有 \(N（1≤N≤300）\) 名应聘者，通过多轮面试和洽谈，越越整理出了每位应聘者期望的薪酬 \(w_i\) 和能够为公司带来的贡献 \(v_i（1≤v_i≤1000）\)。

现在越越想知道在总薪酬不超过 \(W（1≤W≤10^9）\) 的情况下，他所能招聘员工的总贡献最大是多少？

格式

输入格式

第一行两个正整数 \(N\) 和 \(W\)；

以下 \(N\) 行，每行两个正整数 \(w_i\) 和 \(v_i\)，表示一个应聘者期望的薪酬 \(w_i\) 和能够为公司带来的贡献 \(v_i\)。

输出格式

一个正整数，表示最大的总贡献。

样例1

样例输入1

6 15
6 5
5 6
6 4
6 6
3 5
7 2

样例输出1

17

样例解释

应该选择的是第 \(2、4\) 和 \(5\) 应聘者。

限制

时间：\(1s\) 空间：\(256M\)

对于 \(20\%\) 的数据：\(1≤N≤24；1≤W≤1000\)；

对于 \(50\%\) 的数据：\(1≤N≤100；1≤W≤10^4\)；

对于 \(100\%\) 的数据：\(1≤N≤300；1≤W≤10^9；1≤w_i≤W；1≤v_i≤1000\)；

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)