题目描述

某大型卖场在节日期间举行购物竞赛, 参赛者可以推着购物车在卖场中选择提前罗列好的商品, 可选商品有 $N$ 种, 每种商品的总价为 $M$ 元, 被拆分成均等的 $K$ 个包装, 现在购物车里可以装的包装数量被固定为 $L$ 个, 问怎么选才能使购物车中的价值最大。

输入格式

第一行输入整数 $N$ 和 $L$ , 用空格隔开。

第二行到第 $N+1$ 行, 每行两个整数 $M$ 和 $K$ , 用空格隔开。

输出格式

一个整数, 购物车中可以装载的最大价值。

样例1

5 10
12 6
8 2
20 4
7 7
15 5

40

数据范围

$1\le N,L\le 100,1\le M,K\le 100,M\%K=0$