1656: 旅行计划
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：0
题目描述
某教练想做一次旅行，将走高速公路，因为在路旁有一些价格实惠的旅馆，当然要考虑沿途花费尽可能的少（不考虑开始点和到达点）。为了安全起见，他每天只在白天行走，晚上在旅馆住宿，并且一天的路程不超过
【编程任务】
你的任务是编写一个程序，在旅行距离内，对给定的输入数据，求
1）费用最少的旅行计划（即中途住宿的费用之和），如果有多个最小费用计划，则取日程最短的计划。
2）日程最短的旅行计划（中途在旅馆住宿的天数），如果有多个最短日程计划，则取费用最少的计划。
输入
输入文件中的第一行有用一个空格分隔的两个正整数，第一个整数d 表示旅行的距离（单位：公里）；第二个整数 h表示沿途旅社的数目（ d ≤ 16000, h ≤ 1000）。接下来的h行，每行有两个用单个空格分隔的正整数，说明某旅社的相关信息，第一个正整数表示它离起点的距离（单位：公里），第二个正整数表示该旅社的价格。价格不会超过1000。
输出
输出文件的第一行输出费用最少的旅行计划；第二行输出日程最短的旅行计划；旅行计划由在所有住宿的旅社组成，对每个旅社，只输出离出发点的距离即可，相邻两个数之间用一个空格分隔。
样例输入 复制
2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40
样例输出 复制
400 1200
400 1200