题目背景

在穰子收红薯的时候，她的姐姐静叶负责打扫收集秋天散落的落叶。

题目描述

不同种类的落叶装在不同的篮子里。每个篮子里的落叶必须整篮带走，她的背包装载重量有限，总重量不能超过上限。请帮静叶算出：在不超过背包承重的前提下，她最多能收集多少落叶。

输入格式

第一行两个整数 n,W（1≤n≤20，1≤W≤1000） 接下来 n 行，每行两个整数。wi,ci。（1≤w,c≤100） 其中，wi代表落叶的重量，ci代表落叶的数量。

输出格式

一个整数，表示最多能收集的落叶数量。

样例

4 50
10 8
15 12
20 15
8 6

35

样例解释

选择第 2 篮（15 克 / 12 片）+ 第 3 篮（20 克 / 15 片）+ 第 4 篮（8 克 / 6 片），总重量 15+20+8=43 ≤ 50，总数量 12+15+6=35，为最大值。