比赛场次 419
比赛名称 hhh
比赛状态 已结束比赛成绩
开始时间 2018-07-31 10:01:00
结束时间 2018-07-31 13:30:00
开放分组 全部用户
注释介绍
题目名称 韩信点兵
输入输出 HanXin.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar雾茗 AAAAAAAAAA 0.001 s 0.31 MiB 100
Gravatar梦那边的美好ET AAAAAAAAAA 0.048 s 0.31 MiB 100

韩信点兵

★★☆   输入文件:HanXin.in   输出文件:HanXin.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

    韩信是中国军事思想“谋战”派代表人物,被后人奉为“兵仙”、“战神”。“王侯将相”韩信一人全任。“国士无双”、“功高无二,略不世出”是楚汉之时人们对其的评价。作为统帅,他率军出陈仓、定三秦、擒魏、破代、灭赵、降燕、伐齐,直至垓下全歼楚军,无一败绩,天下莫敢与之相争。

    相传,韩信带兵打仗时,从不直接清点军队人数。有一次,韩信带 $1500$ 名兵士打仗,战死四五百人。站 $3$ 人一排,多出 $2$ 人;站 $5$ 人一排,多出 $4$ 人;站 $7$ 人一排,多出 $6$ 人。韩信马上说出人数:$1049$。

    这次,刘邦派韩信带兵 $N$ 人攻打一座重兵驻扎的城市。城市占领了,可汉军也是伤亡惨重。韩信需要知道汉军至少损失了多少兵力,好向刘邦汇报。

    已知韩信发出了 $M$ 次命令,对于第i次命令,他选择一个素数 $P_i$,要求士兵每 $P_i$ 人站一排,此时最后一排剩下了 $a_i$ 人。你的任务是帮助韩信求出这种情况下汉军损失兵力的最小值。当然,由于士兵们都很疲惫,他们有可能站错队伍导致韩信得到的数据有误。

【输入格式】

第一行两个正整数 $N,M$,分别代表最初的军队人数和韩信的询问次数。

接下来有 $M$ 行,每行两个非负整数 $P_i,a_i$,代表韩信选择的素数和此时剩下的人数。

输入保证每个素数各不相同。

【输出格式】

输出一行,一个整数。

若有解,输出最小损失人数。若无解,输出 $-1$.

【样例输入】

1500 3
3 2
5 4
7 6

【样例输出】

31

【数据范围】

对于 30% 的数据,$1 \leq N \leq 1,000,000$,$1\leq M \leq 4$;

对于 50% 的数据,$1 \leq N \leq 100,000,000$,$1 \leq M \leq 8$;

对于 100% 的数据,$1 \leq N \leq 1,000,000,000,000$,$1 \leq M \leq 10$;

保证所有素数的乘积 $\prod_{i=1}^nP_i\le 10^{12}$,$0 \le a_i < P_i$。