g6-08130. 便利店货架 未做

街角便利店的货架最多能摆下总占地 $W$ 个单位的商品。店里有 $n$ 种商品，第 $i$ 种每件占 $w_i$ 个单位、能赚 $v_i$ 元；供货商每天都会把货补满，所以每种商品想摆几件就摆几件。

求这排货架最多能赚到多少利润。

第一行两个整数 $n$、$W$。

接下来 $n$ 行，每行两个整数 $w_i$、$v_i$。

一行一个整数，表示最大总利润。

输入 1

3 8
2 5
4 7
9 20

输出 1

20

第一种商品摆 $4$ 件：占地 $4\times 2=8$ 个单位，利润 $4\times 5=20$ 元。第三种商品单件就要占 $9$ 个单位，货架放不下；第二种摆满也只赚 $2\times 7=14$ 元。

$1\le n\le 1000$，$0\le W\le 10^4$，$1\le w_i\le 10^9$，$0\le v_i\le 10^9$。保证答案不超过 $10^{18}$。