Scroll Compression

You are given n scrolls. Each scroll has a pre-compression length L and a compression factor c. The compressed length of a scroll is computed as \(\lfloor \frac{L}{c} \rfloor\) (i.e. integer division of L by c).

Your task is to compute the minimum total length of all compressed scrolls.

inputFormat

The first line contains an integer n representing the number of scrolls. Each of the following n lines contains two space-separated integers: the pre-compression length L and the compression factor c.

You may assume that 1 ≤ n ≤ 10⁵ and 1 ≤ L, c ≤ 10⁹.

outputFormat

Output a single integer -- the sum of the compressed lengths of all scrolls. Formally, if the compressed length of a scroll is \(\lfloor \frac{L}{c} \rfloor\), output \(\sum_{i=1}^{n} \lfloor \frac{L_i}{c_i} \rfloor\).

4
100 2
300 4
500 2
700 7

475