루벤의 미니언 소환

면접 대비

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

요약

필요한 작업량 W를 채우는 가장 적은 미니언 수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

프로그래밍 대회의 총괄 심사위원 자리는 만만한 일이 아니다. 대회가 열리기 전에 처리해야 할 일이 길게 늘어선다. 다행히 루벤은 버튼을 누르면 자기 일을 대신 해 줄 작은 미니언을 하나씩 만들어 내는 기계를 얻었다. 기계를 켜라고 알려 줄 조수도 한 명 고용했다.

미니언에는 한 가지 문제가 있다. 수가 너무 많으면 잃어버리기 쉽다. 누군가는 미니언을 계속 관리해야 하므로 적을수록 좋다. 기계가 만들어 낸 미니언은 정해진 양만큼 일하고 나면 그대로 소진된다. 재활용 기계가 있기는 하지만 깊고 어두운 숲 어딘가에 숨어 있다.

기계가 만드는 미니언의 작업량은 평균 $\mu$ 와 표준편차 $\sigma$ 를 모두 모르는 정규분포를 따른다. 일정한 시간 동안 기계가 만들 수 있는 미니언의 수는 세기 $\lambda$ 를 모르는 푸아송분포를 따른다.

우리가 알고 싶은 것은 루벤이 모든 일을 끝내려면 미니언을 최소 몇 번 만들어야 하는가이다. 미니언 $M$ 마리가 각각 몇 단위의 일을 할 수 있는지 목록으로 주어진다. 기계는 미니언을 $M$ 마리 만들고 나면 완전히 고장 난다. 다음에 어떤 미니언을 만들지는 목록에서 고를 수 있지만, 같은 미니언을 두 번 만들 수는 없다. 미니언은 저마다 다르지만 작업량은 서로 같을 수 있다.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어지는 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 루벤이 끝내야 하는 일의 양 $W$ 와 기계가 만들 수 있는 미니언의 수 $M$ 이 주어진다. 다음 줄에는 각 미니언이 할 수 있는 일의 양 $C_i$ 가 $M$ 개 주어진다.

$0 < T \le 50$
$0 < W \le 10000$
$0 < M \le 100$
$0 < C_i \le 100$

출력

각 테스트 케이스마다 일의 양 $W$ 를 모두 끝내는 데 필요한 미니언의 최소 개수를 한 줄에 출력한다. 미니언을 $M$ 마리 다 만들어도 $W$ 를 채울 수 없으면 따옴표 없이 no rest for Ruben을 출력한다. Ruben의 첫 글자 R은 대문자로 써야 한다.

예제4

예제 1

입력

4
4 5
1 2 4 100 3
10 10
1 1 1 1 1 1 1 1 1 1
20 10
9 1 1 1 1 1 1 1 1 9
100 5
81 1 2 1 4

예상 출력

1
10
4
no rest for Ruben

예제 2
입력
```
1
1 1
1
```
예상 출력
```
1
```
예제 3
입력
```
1
1 1
100
```
예상 출력
```
1
```
예제 4
입력
```
2
15 5
5 5 5 5 5
16 5
5 5 5 5 5
```
예상 출력
```
3
4
```