A huge storm is ravaging the world and as you and your family run away from it, you come across a gigantic shelter run by a girl. She tells you that "she sells sanctuary" and that different types of rooms are offered at different prices.
A room may only house one person.
Write a program which takes in two inputs: the number of people staying at the sanctuary and an array, map, object or string, whatever is convenient as long as the structure is similar to:
[[2, 3], [3, 5], [6, 7]]
In this case, it's a two dimensional array, but it could be a string, like
2,3 3,5 6,7
For each entry, the first item is the number of rooms offered for that type, and the second item is the cost of one room. For instance,
[[1, 2], [3, 4]]
means that one room is offered for the first type for 2 dollars each, and three rooms for the second type at 4 dollars each.
Since your family has limited resources, you would like to find the configuration for which as little money is spent as possible. So, your program should output a few numbers containing information about the number of rooms. At the end, it should also output the total cost.
This might all sound confusing, so take a sample input:
First input: 5 Second input: [[2, 5], [2, 3], [7, 100]]
The cheapest possible configuration is to have two people stay in the first type, costing
3 * 2 = 6 dollars, then two people in the second type for
5 * 2 = 10 dollars, and one person in the last type, for
100 * 1 = 100 dollars. The total cost is therefore
116 dollars. Your output for this test case would be
2 // two people in the first type of room 2 // two people in the second type of room 1 // one person in the third type of room 116 // total cost
Let us try another.
first input: 10 second input: [[1340993842, 5500], [1, 5000]]
The cheapest configuration is to have one person stay in the second type, and the other nine in the first type. The cost is therefore
9 * 5500 + 1 * 5000 = 54500.
9 1 54500
A few extra rules:
- The number of people staying will never be more than the total number of rooms.
- Standard loopholes are disallowed as usual.
- The last output must be the price.
- You may output as an array if you would like.
- Nobody else is staying in the sanctuary.
- Shortest answer in bytes wins because this question is code-golf.
- Input may be taken as rest parameters.
- Order may be reversed, so for example the price might be the first item. You must make it clear though.
- The rooms are not guaranteed to be ordered from cheapest to most expensive.
- Output must be in order of the types given