题目背景

你在经营一家魔法药剂店。店里有 $n$ 种基础材料，每种材料有固定的"魔力值"和"单位重量"。

制作一瓶药剂相当于选取若干份材料混合（可以多次使用同一种材料），所有材料的总重量不能超过药瓶的容量 $C$。你希望配制出的药剂总魔力值最大。

题目描述

给定药瓶容量 $C$，以及 $n$ 种材料的各自单位重量 $w_i$ 和魔力值 $v_i$。

每种材料可以使用任意多次，求在总重量不超过 $C$ 的前提下，能获得的最大总魔力值。

输入格式

第一行两个整数 $n, C$。

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

输出格式

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

样例输入

3 15
6 10
4 7
3 5

样例输出

26

样例解释

三种材料：

最优方案：$3$ 份材料 B（重量 $12$，魔力 $21$）+ $1$ 份材料 C（重量 $3$，魔力 $5$），总重量 $15$，总魔力 $26$。

也可以 $1$ 份材料 A + $3$ 份材料 C（重量 $15$，魔力 $25$），但不如 $26$ 大。

数据范围

$1 \le n \le 100$，$1 \le C \le 10000$，$1 \le w_i, v_i \le 1000$。