问题 23692. -- QiQi and Travel

23692: QiQi and Travel

时间限制: 1 Sec  内存限制: 128 MB
献花: 25  解决: 11
[献花][花圈]

题目描述

QiQi想做一次旅行,在路旁边有些旅馆,QiQi每行走800公里就要住一次旅馆,现在给出旅馆的信息,包括每个旅馆距离起点的距离和每个旅馆的价格。现在你有两个任务:

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

提示

来源

[献花][花圈]