题目描述

卡卡西购买了一批图书后，非常的高兴，爸爸妈妈也表扬了他，称赞他把零用钱用到了最需要使用的地方，但卡卡西发现如果再购买一些文具送给贫困山区的小朋友们就更好了。第二天，卡卡西发动自己的小伙伴拿出他们的零用钱去购买文具，文具以套为单位，按包装销售，每个包装中有数量不等的文具，而且价格也不一样，卡卡西和小伙伴们只想购买一种包装的文具，商店不允许他们将包装拆开，因此卡卡西有可能需要购买超过 n 套文具才行，在商店每种包装的数量都足够的情况下，要买够至少 n 套文具最少需要花费多少钱。

输入输出格式

输入

输入数据共 m+1 行。 第一行有两个用空格分隔的正整数 m，n。m 表示包装的数量，n 表示需要购买的套数。 接下来的 m 行，每行有两个用空格分隔的正整数 s1, s2，分别表示每一种包装中文具的数量和整包的价格。

输出

一个正整数，表示买够至少 n 套文具的最少花费。

输入输出样例

样例

输入1

3 60
3 5
16 20
31 35

输出1

70

数据范围/约定

1s, 256MB.

1≤m≤1000 1≤n，s1，s2≤10000