Alena packs things for vacation. She can take hand luggage and luggage with her on the plane. For hand luggage, Alena has a backpack, and for luggage – huge suitcase.
According to the rules of transportation, the weight of hand luggage should not exceed S kg, and luggage can be of any weight (Alena is ready to pay extra for excess luggage). Of course,
the most valuable things – laptop, camera, documents, etc. – Alena wants to put in hand luggage.
Alena has arranged all her belongings in order of decreasing value and begins to put the most valuable things in her backpack. She acts as follows – takes
the most valuable item, and if its mass does not exceed S, then puts it in a backpack, otherwise puts it in a suitcase. She then takes the next highest value item, if possible
put in a backpack, that is, if its mass, together with the mass of things already put in a backpack, does not exceed S, then puts it in a backpack, otherwise in a suitcase, and in the same way the process
continues for all items in descending order of their value.
Determine the weight of the backpack and suitcase after Alyona folds everything.
The first line of the input contains the number S – the maximum allowed weight of the backpack. The second line of the input contains the number N – number of items.
The next N lines give the masses of the items, the items themselves are listed in descending order of value (the mass of the most valuable item is indicated first, then the mass of the second in
the value of the subject, etc.). All numbers are natural, the number S does not exceed 2x10
9, the sum of the weights of all objects also does not exceed 2x10
9. The value of N does not exceed 10
5.
The program should output two numbers – the weight of the backpack and the weight of the suitcase (the weight of an empty backpack and suitcase is not taken into account).
Examples
| # |
Input |
Output |
Explanation |
| 1 |
20
5
6
10
5
2
3 |
18 8 |
The maximum possible weight of the backpack is 20 kg. Given 5 items weighing 6, 10, 5, 2, 3.
First, an item with a weight of 6 is placed in the backpack, then an item with a weight of 10 is also placed in the backpack. Item
weighing 5 cannot be put in a backpack, because then the weight of the backpack will become 21 kg, so an item weighing 5
put in a suitcase. Then an item weighing 2 is placed in the backpack, and an item weighing 3 – in a suitcase. Weight
backpack 6 + 10 + 2 = 18, suitcase weight 5 + 3 = 8. |