P13413 [COCI 2012/2013 #4] OREHNJACA

最近，电视台开始录制新一季的 **Jamie Oliver** 烹饪节目。本季中，Jamie 计划向全世界展示克罗地亚美食的魅力。在第一期节目中，这位大厨烘焙了一条长达 $L$ 米的核桃卷，这是该地区有史以来最长的核桃卷。经过长时间的辛勤烹饪，他决定奖励在场的 $N$ 位忠实观众。 他将核桃卷切成每段 $1$ 米的小段，并从左到右依次编号为 $1$ 到 $L$。每位观众都获得了一个唯一的编号 ID（从 $1$ 到 $N$ 的正整数），以及一张写有两个整数 $P$ 和 $K$ 的纸条。每位观众随后可以领取从第 $P$ 段到第 $K$ 段（包含两端）的所有核桃卷。观众按照 ID 编号的顺序依次领取（编号为 $1$ 的观众先领，然后是编号为 $2$ 的观众，依此类推）。由于领取顺序的影响，有些观众实际拿到的核桃卷段数比他们原本预计的要少。下表对应于第一个样例测试： | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |---|---|---|---|---|---|---|---|---|----| | | 1 | 1 | 1 | | 3 | 2 | 2 | 3 | | 请编写程序，确定哪位观众**期望**获得最多的核桃卷段，以及哪位观众**实际**获得的核桃卷段最多。

输入的第一行包含一个正整数 $L$（$1 \leq L \leq 1000$），表示核桃卷的长度。 第二行包含一个正整数 $N$（$1 \leq N \leq 1000$），表示观众人数。 接下来 $N$ 行，每行包含两个正整数 $P_i$ 和 $K_i$（$1 \leq P_i \leq K_i \leq L$，$i = 1..N$），分别表示第 $i$ 位观众纸条上的 $P$ 和 $K$。

输出两行。 第一行输出**期望**获得核桃卷段数最多的观众编号。 第二行输出**实际**获得核桃卷段数最多的观众编号。 如有多名观众满足条件，输出编号最小的那一位。

如果第一行输出正确，则该测试点可获得 60% 分数；如果第二行输出正确，则该测试点可获得 40% 分数。 翻译由 ChatGPT-4.1 完成。