Background

Special for beginners, ^_^

问题描述

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

Input

第一行输入整数N和L，用空格隔开。（1≤N,L≤100） 第二行到第N+1行，每行两个整数M和K，用空格隔开。 1≤M,K≤100,M%K=0）

Output

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

Samples

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

40

Limitation

1s, 1024KiB for each test case.