0 人解决，1 人已尝试。
0 份提交通过，共有 1 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
A coach trip by a transcontinental motorway lasts many days so payments for hotels are a serious part of the travel cost.
For the sake of safety and comfort coaches travel only in the daytime and can make at most 800 km a day. During the trip the
driver and passengers spend nights in hotels (it does not concern the beginning and the end of the trip). So far travels were
planned to minimize the number of nights spent in hotels. To decrease the cost the firm organizing travels decided to find out
if it is commercially viable to plan the travels in such a way that the sum of payments for hotels is minimal (even if it extends
the time of travel). Offers of hotels situated along the motorway should be used in calculations. Each offer consists of the
distance between the hotel and the beginning of the route and the price of a single night for one person in the hotel. The travel
is one-way. The route does not fork. At each point of the route the coach is only once. To identify a hotel it is enough to give its
distance from the beginning of the route, i.e. at each point of the route there is at most one hotel. Nights at the beginning and at
the end of the route are not planned. The number of passengers is constant and in every hotel all of them and the driver pay for
the night the same amount - according to the offer. We assume that the capacities of hotels are big enough to place all the passengers.
There is at least one hotel in every fragment of the route of length 800 km, so travel can be always made according to the given conditions.
Write a program that:
* reads the following data: the length of the route, the number of hotels and the offers of hotels; * finds two plans of travel: @ a plan of the cheapest travel (the sum of payments for hotels is minimal); if there is more than one solution the program should chose the one with the minimal number of nights in hotels, @ a plan of the shortest travel (the number of nights in hotels is minimal); if there is more than one solutions the program should chose the one with the minimal sum of payments for hotels; * writes the results, i.e. two plans of travel - the cheapest and the shortest.
In the first line there are written two positive integers separated by a single space. The first integer d is the length of the
route given in kilometres. The second integer h is the number of hotels, d <= 16000, h <= 1000. In the following h lines there
are written the offers of hotels - one offer in one line. The offers are ordered according to the increasing distance of hotels from
the beginning of the route. Each offer consists of two positive integers separated by a single space. The first integer is the
distance of the hotel from the beginning of the route and is given in kilometres. The second integer is the price of a single night
in this hotel and is not greater than 1000.
In the first line there should be written the plan of the cheapest travel, i.e. the distances from the beginning of the route of
the hotels in which we decide to spend nights. In the second line there should be written, in a similar way, the plan of the
shortest travel. The numbers in each line should be separated by a single space.
2000 7 100 54 120 70 400 17 700 38 1000 25 1200 18 1440 40
400 1200 400 1200
0 人解决，1 人已尝试。
0 份提交通过，共有 1 份提交。
9.9 EMB 奖励。