仓库编号（warehouse）

题目描述

某仓库中共有 (n) 种物资。

第 (i) 种物资的重量为$(w_i)，价值为 (v_i)。$

仓库会先将所有物资按照重量从小到大排序，并从 1 开始重新编号。

重量相同时，按照输入顺序排列。

仓库采用以下供应规则：

• 重新编号为奇数的物资，最多只能领取一件。
• 重新编号为偶数的物资，库存充足，可以领取任意非负整数件。

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

要求装入物资的总重量不超过 (V)。

求运输箱能够装入的物资的最大总价值。

输入格式

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

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

输出格式

输出一个整数，表示最大总价值。

输入输出样例 #1

输入

4 10
5 9
2 3
4 7
3 5

输出

18

样例解释

排序后，四种物资的重量依次为 (2,3,4,5)。

其中编号 2 和 4 的物资可以重复选择。

可以选择两件重量为 5、价值为 9 的物资，得到总价值 18。

数据范围

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