Merging Arithmetic Sequences (II)

Problem Description

There are $n$ arithmetic sequences; the $i$-th sequence can be written as $k_i \times x + b_i$ (with $x = 0, 1, 2, \dots$).

Now answer this: when all these sequences are merged in ascending order, what is the sum of the first $m$ numbers (a number that appears repeatedly is counted each time it appears)?

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers, $k_i$ and $b_i$.

The last line contains an integer $m$.

Output Format

Output one number, the answer.

Sample Input

2
1 2
5 2
8

Sample Output

36

Sample Explanation

The two sequences are $2, 3, 4, 5, 6, 7, 8, \dots$ and $2, 7, 12, \dots$ respectively.

Constraints

For $100\%$ of the data: $1 \leq n \leq 100000$, $1 \leq m \leq 100000$, $1 \leq k_i, b_i \leq 1000$.