合并数列2

题目描述

有 $n$ 个线性序列，第 $i$ 个序列可以表示成 $k_i \times x+b_i$ 的形式（ $x=0, 1, 2,…$ ）。

现在询问将这些序列的数从小到大合并起来，前 $m$ 个数的和是多少（重复出现的数合并后也会多次出现）。

输入第一行一个数 $n$ 。

接下来 $n$ 行每行两个数表示 $k_i, b_i$ 。

最后一行一个数 $m$ 。

输出一个数表示答案。

两个数列分别为 $2, 3, 4, 5, 6, 7, 8, …$ 和 $2, 7, 12, …$ 。

对于 $100\%$ 的数据，保证 $1\leq n\leq 100000, 1\leq m\leq 100000, 1\leq k_i, b_i\leq 1000$。