题目描述
SYH最近得到了学校的奖金,高兴之余SYH决定请实验室的同学吃饭。
抱着不浪费的美好传统,SYH事先统计了所有同学的饭量.
又通过特殊方式了解到了餐厅所有饭菜的单价和份量,每份饭菜只能买一份。
现在SYH想在所有同学恰好吃饱的前提下使花费最大(SYH想让同学们吃顿好的),他想请你帮他解决这个问题。
输入描述
第一行为n,m分别表示餐厅饭菜的种类和所有同学的饭量;
接下来的2-n+1行,每行给出两个整数vi,wi,分别表示每份饭菜的单价和份量。
输出描述
如果所有同学恰好吃饱,输出最大花费。否则,输出-1。
样例输入
5 100 10 29 6 25 11 30 7 23 25 41
样例输出
46
数据范围
$1<=n<=1000,0<=m<=100000,0<=vi,wi<=1000$