礼品封装（gift）

题目描述

商店准备制作一批礼品包。

共有 (n) 件不同的礼品，第 (i) 件礼品的重量为 $(w_i)，价值为 (v_i)$。

工作人员首先按照礼品重量从小到大排序。

如果重量相同，则按照输入中的先后顺序排列。

排序后，工作人员依次将相邻的两件礼品封装成一个礼品包：

• 第 1 件与第 2 件组成第 1 包；
• 第 3 件与第 4 件组成第 2 包；
• 以此类推。

如果 (n) 是奇数，那么最后剩余的一件礼品单独封装成一个礼品包。

封装完成后，礼品包不能拆开。每个礼品包最多只能选择一次。

每个礼品包的重量和价值，分别等于其中所有礼品的重量之和、价值之和。

现在有一个最大承重为 (V) 的运输箱。

请计算能够获得的最大礼品总价值。

输入格式

第一行包含两个整数 (n,V)。

接下来 (n) 行，每行包含两个整数$(w_i,v_i)$。

输出格式

输出最大总价值。

输入输出样例 #1

输入

5 11
5 10
2 3
4 7
3 5
6 12

输出

20

样例解释

按重量排序后的礼品为：

(2,3)、(3,5)、(4,7)、(5,10)、(6,12)

其中每个括号表示 (重量,价值)。

封装后：

选择第 1 包与第 3 包，总重量为 (5+6=11)，总价值为 (8+12=20)。

数据范围

• $(1\le n\le100)$
• $(1\le V\le2000)$
• $(1\le w_i\le2000)$
• $(1\le v_i\le10000)$