Brewing Tea

Interview

Time limit1sMemory limit1024 MB

Summary

Given K bags whose capacities are x_i and pots holding at most 10 cups, find the minimum number of pots that together serve at least N people, where each pot holds tea from a single bag.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Math
Solved: No attempts yet

Problem

Egon is going to brew a lot of tea for $N$ programming olympiad participants. He has $K$ tea bags, all of different kinds. Bag $i$ holds tea for $x\_i$ people. It is guaranteed that the bags together hold tea for at least $N$ people.

Egon plans to use teapots that hold tea for at most 10 people. Since the bags are of different kinds, several bags cannot be mixed in the same pot. However, the same bag can be used for several pots. How many pots does Egon have to use?

Input

The first line contains two integers $1 \le K \le 10$ and $1 \le N \le 100$ , the number of tea bags Egon has and the number of programming olympiad participants. The second line contains $K$ integers $1 \le x\_1, x\_2, \dots, x\_K \le 100$ , the number of people each bag holds tea for.

Output

Print a single integer: the smallest number of teapots Egon has to use.

Hint

In example 1, Egon brews two pots from the first tea bag and two pots from the third tea bag. That gives $20+17$ cups of tea, which is enough for the 36 participants.

In example 2, the optimal choice is to brew six pots from the first tea bag, three pots from the third tea bag, and two from the fourth tea bag. That gives $54+30+16$ cups of tea, which is enough for the 100 participants.

Examples2

Example 1
Input
```
3 36
23 5 17
```
Expected output
```
4
```
Example 2
Input
```
4 100
54 2 33 16
```
Expected output
```
11
```