1636: 芒果
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
有n个牛头人，他们很无聊，决定玩游戏。
他们排成了一队，然后顺序来到一堆准备好的芒果前面，首先从中取出Ai个，然后将剩下的芒果恰好平均分成Bi堆，从中取出一堆，剩余合并成一堆给后来人取；如果当前已经没有芒果了，牛头人会当他已经取过了。当n个牛头人都取一次之后，他们惊奇地发现芒果恰好被分光啦。因为某种关系，对于每只牛头人都有m种决策，他会随机从中取出一种可行的决策。现在他们想知道一开始的时候可能有多少芒果，于是他们找到了你，你能告诉他们吗？这个数字可能很大，所以你只需要告诉他们第k小的可能的芒果数。
如果出现数芒果过程不同但答案相同，我们认为它仅仅是一组解。
输入
输入数据的第一行包括3个正整数n, m, k，分别如题目中所描述。
接下来有m行，每行有2个正整数，表示Ai和Bi。其中Bi一定大于1。
输出
输出一个数表示第k小的芒果数。如果不存在则输出“-1”。
样例输入 复制
3 2 4
1 3
2 2
样例输出 复制
6提示
【样例说明】
前4小的可能芒果数是1，2，4，6。
【数据规模】
对于30%的数据，答案不超过10000；
对于100%的数据，n不超过100，m不超过10，A和B不超过100，k不超过10000。
对于所有的n超过10的数据，Bi的值至少为5。
数据保证答案一定在10^16之内！