题目描述

平凡的某一天，和往常一样。     但也从没有人说过只有在特殊的日子才能送礼物给重要的人。     JZH决定送ZQC一些礼物，没有为什么，只是想。     好吧，一定要说为什么的话，也许是在那天早上看见她在书店门口早早的等着，背着手低着头略带害羞的紧张模样的时候、也许是在那天中午，她靠着他的肩坐在公园的长椅上，一边耳语一边对野猫投食的时候、也许是在那天黄昏，他们在天台上迎着夕阳纵览整个城市的时候、也许是在那天晚上，他们一起仰面躺在草坪上，看着那耀眼的银河，一起找着星座的时候。    也许就是这些时刻，那心中泛起的悸动，让JZH做出了这样的决定。

   因为JZH已经对ZQC非常熟悉了，所以他能估算出ZQC收到对应礼物后的满意度。    JZH到了商店的货架，货架上共有n种礼物可选，第n种礼物只有an个且ZQC对这种礼物的满意度为bn，同一种礼物可以送多次。但JZH并不富有，所以他最多只能拿m个礼物，他希望能知道这m件礼物能让ZQC的满意度最多为多少。

输入格式

第一行有2个正整数n  m（11） 接下来共有n行输入 第n行包含两个整数 an bn  分别代表这种礼物有多少个和ZQC对这种礼物的满意度（0

输出格式

输出一个整数，代表JZH买了不超过m个礼物后ZQC最多能获得的满意度。

3 5
2 5
3 1
2 10

31

提示

有些礼物ZQC收到了会不满意哦~