题目描述

现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值 $v$ 和重量 $w$ $(1 \le v,w \le 10)$ ；如果给你一个背包它能容纳的重量为 $c$ $(10 \le c \le 20)$ ；你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

输入格式

第一行有两个正整数 $n(1 \le n \le 20)$ ， $c$ ； $n$ 表示有 $n$ 个物品，接下来 $n$ 行每行有两个正整数 $v$ ， $w$ 。

输出一行，一个整数，表示背包内的物品的价值和。