1630: [2022SFPC경북pre] 독도 새우잡이1
실행시간 제한: 1 Sec 메모리사용 제한: 128 MB제출: 9 통과: 3
<<--이전 문제 소스 제출 다음 문제-->>
문제 설명
독도와 울릉도에는 도화새우, 물렁가시붉은새우, 가시배새우로 3종류의 독도새우가 서식하고 있다.
독도새우는 달짝지근한 맛과 쫄깃한 식감을 가진 뛰어난 진미로서 많은 사람에게 각광을 받고 있지만, 독도새우를 멸종시키지 않기 위해서는 어획량을 정확하게 조절해야 할 필요가 있다.
비버는 3종류의 통발을 사용하여 독도새우를 잡고 있다. 비버가 사용하는 통발은 정확하게 정해진 수만큼의 새우를 잡을 수 있다.
비버가 허용된 어획량을 정확하게 지키면서, 최소 개수로 통발을 내려 독도새우를 잡을 수 있는 방법을 알아보자. 그리고 통발을 최소 횟수로 내려야만 어업 시간뿐만 아니라, 독도 주변 해양 생태계도 보호할 수 있다.
입력 설명
첫 번째 줄에는 독도와 울릉도 근처의 새우 수(n)가 입력된다.
두 번째 줄에는 유지해야 하는 최소 새우 수(m)가 입력된다.
세 번째 줄에는 통발을 한 번 사용하였을 때 잡을 수 있는 3가지 마릿 수(d1, d2, d3)가 스페이스로 구분되어 입력된다.
(1 <= n <= 105)
(1 <= m <= 105, m<=n)
(1 <= d1 <= 104)
(1 <= d2 <= 104)
(1 <= d3 <= 104)
출력 설명
유지해야 하는 최소 새우 수를 정확하게 지키면서 허용된 새우를 모두 잡기 위해 사용한 통발을 최소 개수를 출력한다.
단, 허용된 새우를 어획하는 방법이 없는 경우에는 -1을 출력한다.
입력 예시 Copy
50000
30000
1000 3000 5000
출력 예시 Copy
4
도움
입력 예시2
55000
50000
500 1000 1500
출력 예시2
4
입력 예시3
55300
50000
500 1000 1500
출력 예시3
-1