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

请问将这些序列的数合并起来后，第 $m$ 小的数是多少（重复出现的数合并后也会多次出现）。

输入格式

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

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

最后一行一个数 $m$。

输出格式

输出一个数表示答案。

样例输入

2
1 2
5 2
8

样例输出

7

数据规模

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