猴子和香蕉

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 monkeys.in 输出文件 monkeys.out

【问题描述】

你听说过猴子分香蕉的故事吗?这个题目有些不一样.有N只猴子住在一个岛屿上,一天他们发现了很多香蕉,于是他们决定把这些香蕉分成各自的,他们应该怎么做?
吵闹了很长时间,他们制定了如下规则:他们定出了C条选择,每个选择包含两个整数x,y,我们假设开始有B串香蕉,每只猴子从老的到小的,随机进行一个选择获得他自已的香蕉.如果他选了第i个选择(1≤i≤C),他可以先得到yi串香蕉,然后,他把剩余的分成xi堆,每堆是相同的.最后他再获得一堆香蕉.他总共获得了yi和一堆香蕉.每只猴子都这样做.当最后一只猴子选择时,他们发现所有的香蕉都分完了.
现在我知道他们的计划.但我不知道哪只猴子作了什么选择,也不知道猴子和香蕉的开始数量.如果有B0串香蕉能满足这个分配过程,B0被认为是一个可能的答案.
这是你的工作,我将给你一个数K,你应该输出第K小的可能的答案.
【输入格式】
输入文件第一行是两个正整数Nm(Nm≤100)和C(C≤20)，表示猴子的最大数量和他们的选择数．下面每行包含两个整数xi(2≤xi≤100)和yi(0≤yi≤100)，含义如题所述．下面一行包含一个整数K (1≤K≤1,000,000),是I号请求．
【输出格式】

输出仅一行包含一个整数B，是一个与输入需求一致的答案．如果K是一个比所有答案大的数,则输出“-1” .
注意:已知香蕉总数不会超过10^9．

【输入样例】
输入文件名：monkeys.in
2 2
2 4
3 2
3
输出文件名：monkeys.out
5
输入文件名：monkeys.in
2 2
2 4
3 2
6
输出文件名：monkeys.out
-1