题目描述

有n个物体，每个重量和价值都各不相同，请在总重量不超过c的基础上让总价值尽量高。

每一个物体都可以只取走一部分，价值和重量按比例计算。

输入格式

输入包含n+2行：

第1行包括一个整数n，表示物体的数量(n<10000)。

第2行包括一个整数c，表示重量限制(c<10000)。

第3~n+2行每行包含两个整数，分别为每个物体的重量和价值。

输出格式

选择物体的总价值。

样例数据

input

3
20
5 100
15 90
15 10

output

190