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.

The challenge
=============

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`.
Output:

```
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](/questions/tagged/code-golf "show questions tagged '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