小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。 小度有一些钞票资金, 一共有n种不同的面额, 对于面额为的钞票, 小度有张, 并且每一个钞票面额都能整除所有比它大的面额, 并且每一张钞票不能找零。 小度想知道这部分资金最多能牛牛发放多少个月的工资?

输入描述:

包括n+1行,第一行包括两个正整数。接下来的n行, 每行两个正整数, 即面额和该面额所拥有的钞票数量。

输出描述:

一个整数，表示最多能支付多少个月工资。