记录编号	397835	评测结果	AAAAAAAAAAAAAT
题目名称	575.猴子和香蕉	最终得分	92
用户昵称	confoo	是否通过	未通过
代码语言	C++	运行时间	3.253 s
提交时间	2017-04-20 22:08:14	内存使用	15.55 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define fa (o>>1)
const int C = 25, N = 2e6 + 1, INF = 2e9;
int n, m, k, x[C], y[C], st[N], sz, pos[C], dep[N];
int extend(int i) {
	if (pos[i] + 1 > sz) return INF;
	for (;pos[i] + 1 <= sz && (long long)st[pos[i] + 1]*x[i]%(x[i] - 1); pos[i]++);
	return pos[i] + 1 <= sz ? (long long)st[pos[i] + 1]*x[i]/(x[i] - 1) + y[i] : INF;
}
int main() {
	freopen("monkeys.in", "r", stdin);
	freopen("monkeys.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i= 1; i <= m; i++) scanf("%d%d", x + i, y + i);
 	st[++sz] = 0;
	scanf("%d", &k);
	k++;
	for (; sz < k;) {
//#define DBG
#ifdef DBG
		for (int i = 1; i <= sz; i++) printf("%d(%d) ", st[i], dep[i]);
		putchar('\n');
#endif
		int mn = 2e9, mp;
		for (int i = 1; i <= m; i++) {
			int x;
			if ((x = extend(i)) < mn) {
				mp = i;
				mn = x;
			}
		}
		if (mn == 2e9) break;
		else {
#ifdef DBG
			printf("%d from %d through %d\n", mn, st[pos[mp] + 1], mp);
#endif
			if (st[sz] == mn) dep[sz] = std::min(dep[sz], dep[pos[mp] + 1] + 1);
			else if (dep[pos[mp] + 1] + 1 <= n) st[++sz] = mn, dep[sz] = dep[pos[mp] + 1] + 1;
			pos[mp]++;
		}
	}
	printf("%d\n", sz == k ? st[sz]: -1);
}