灌水(water.pas/c/cpp)
炎热的夏季,新疆吐鲁番地区又赢了一年中最难熬的旱季。作为一个经验充分的农夫,约翰在旱季来临之前购买了大量不同体积的水桶,用于存储灌溉农田的用水。约翰有一个葡萄园,他每天必须给所有葡萄浇灌C升的水,以防止它们因为缺水而枯萎。
已知约翰有体积为Vi的水桶mi个,并且每个水桶都灌满了水。有个不幸的消息时,一个水桶一旦开封后,里面的水必须一次性用完,就算当天不需要如此大量的水,桶里的水也会因为炎热的天气而被蒸发干净。这些水桶的体积的最大公约数为水桶的最小体积。
求问约翰存储的水可以使用多少天。
[输入格式]
第一行,两个正整数N(1<=N<=20)和C(1<=C<=100,000,000)。
第2~N+1行,每行两个整数,表示水桶的体积V(1<=V<=100,000,000)和水桶的数量M(1<=M<=1,000,000)。
[输出格式]
一个整数,代表可以灌溉的天数。
[样例输入]
3 6
10 1
1 100
5 120
[样例输出]
111 |