题目描述

有$n$个线性序列，第$i$个序列可以表示成$k_i×x+b_i$的形式$（x=0,1,2...）$。 请问将这些序列的数合并起来后，第 $m$ 小的数是多少 (重复出现的数合并后也会多次出现)。

输入格式

第一行一个数$n$。 接下来$n$行每行两个数表示$k_i,b_i$。 最后一行一个数$m$。

输出格式

输出一个数表示答案。

样例 #1

样例输入 #1

2
1 2
5 2
8

样例输出 #1

7

提示

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