比赛场次	94
比赛名称	20110727
比赛状态	已结束比赛成绩
开始时间	2011-07-27 08:00:00
结束时间	2011-07-27 13:00:00
开放分组	全部用户
注释介绍

题目名称	猴子和香蕉
输入输出	`monkeys.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	14 简单对比

用户	结果	得分
ybh	AAAAAAAWAAAWAA	85
.Xmz	AAAAAAAATAATTT	71
PurpleShadow	AAAAAAAATAATTT	71
老虎小飞	AAAAAAAEEAAEEE	64
苏轼	AAAAAAAWTAATTT	64
reamb	AAAAWAWEEAAWEE	50
ZhouHang	AAWAWAWEEWAEEE	35
Yoghurt	AAWAWAWWTWAWTT	35
lizhe	WAWAWAWWWWAWWW	28
Pom	WAWAWAWWWWAWWW	28
Citron酱	WAWAWAWWWWAWWW	28
wo shi 刘畅	WAWAWAWWWWAWWW	28

猴子和香蕉

★★☆ 输入文件：monkeys.in 输出文件：monkeys.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

你听说过猴子分香蕉的故事吗?这个题目有些不一样.有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

输入文件名：monkeys.in

2 2
2 4
3 2
6

输出文件名：monkeys.out

-1