티 우리기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 주머니가 x_i명분의 차를 담고 있고 주전자 하나에는 최대 10명분만 우릴 수 있을 때, N명분 이상을 만들기 위해 필요한 최소 주전자 수를 구한다. 한 주전자에는 한 종류의 주머니만 쓴다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

Egon은 프로그래밍 올림피아드 참가자 $N$ 명에게 줄 차를 많이 우리려고 한다. 그는 서로 다른 종류의 티백 $K$ 개를 가지고 있다. $i$ 번째 티백으로는 $x\_i$ 명분의 차를 만들 수 있다. 모든 티백을 합치면 적어도 $N$ 명분은 된다.

Egon은 최대 10명분의 차를 담을 수 있는 주전자를 사용하려고 한다. 티백의 종류가 서로 다르므로 같은 주전자에 여러 티백을 섞을 수는 없다. 하지만 같은 티백을 여러 주전자에 나누어 쓸 수는 있다. Egon은 주전자를 몇 개 사용해야 하는가?

입력

첫째 줄에 두 정수 $1 \le K \le 10$ 과 $1 \le N \le 100$ 이 주어진다. 이는 Egon이 가진 티백의 수와 프로그래밍 올림피아드 참가자의 수이다. 둘째 줄에 $K$ 개의 정수 $1 \le x\_1, x\_2, \dots, x\_K \le 100$ 이 주어지며, 이는 각 티백으로 만들 수 있는 차의 인원수이다.

출력

Egon이 사용해야 하는 최소 주전자 수를 정수 하나로 출력한다.

힌트

예제 1에서 Egon은 첫 번째 티백으로 주전자 두 개, 세 번째 티백으로 주전자 두 개를 우리기로 한다. 그러면 $20+17$ 잔의 차가 나오고, 이는 참가자 36명에게 충분하다.

예제 2에서는 첫 번째 티백으로 주전자 여섯 개, 세 번째 티백으로 주전자 세 개, 네 번째 티백으로 주전자 두 개를 우리는 것이 최적이다. 그러면 $54+30+16$ 잔의 차가 나오고, 이는 참가자 100명에게 충분하다.

예제2

예제 1
입력
```
3 36
23 5 17
```
예상 출력
```
4
```
예제 2
입력
```
4 100
54 2 33 16
```
예상 출력
```
11
```