| 比赛场次 | 132 |
|---|---|
| 比赛名称 | 20120418x |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2012-04-18 14:15:00 |
| 结束时间 | 2012-04-18 17:30:00 |
| 开放分组 | 全部用户 |
| 注释介绍 |
| 题目名称 | 猴子和香蕉 |
|---|---|
| 输入输出 | monkeys.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 14 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 201101 |
AAAAAAAAEAATTE | 0.000 s | 0.00 MiB | 71 |
 TBK |
AAAAAAATTAATTT | 0.000 s | 0.00 MiB | 64 |
 Makazeu |
AAAAAAATTAATTT | 0.000 s | 0.00 MiB | 64 |
 王者自由 |
AAWAWAWEEWAEEE | 0.000 s | 0.00 MiB | 35 |
 kaaala |
WAWAWAWWTWATTT | 0.000 s | 0.00 MiB | 28 |
 日光。 |
C | 0.000 s | 0.00 MiB | 0 |
【问题描述】
你听说过猴子分香蕉的故事吗?这个题目有些不一样.有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
2 4
3 2
3
输出文件名：monkeys.out
5
输入文件名：monkeys.in
2 2
2 4
3 2
6
2 4
3 2
6
输出文件名：monkeys.out
-1