공동 구매의 결제 상한

문제

한 온라인 쇼핑몰에서는 공동 구매 행사를 준비하고 있다. 행사에 참여할 주문 N개는 이미 확정되어 있고, 각 주문에는 할인 전 결제 금액이 정해져 있다. 쇼핑몰은 주문마다 다른 할인율을 정하는 대신, 행사 전체에 하나의 결제 상한 C를 적용하려고 한다. 결제 상한은 0 이상 9,999 이하의 정수여야 한다. 할인 전 결제 금액이 P인 주문에 상한 C를 적용하면 실제 결제 금액은 P와 C 중 작은 값이 된다. 예를 들어 할인 전 금액이 700인 주문에 상한 500을 적용하면 500을 결제하고, 할인 전 금액이 300인 주문에는 같은 상한을 적용해도 300을 결제한다. 상한을 0으로 정하면 모든 주문의 실제 결제 금액은 0이 된다. 모든 금액은 같은 정수 단위를 사용하며, 추가 수수료나 배송비는 없다. 쇼핑몰은 이번 행사에서 실제 결제 금액의 합이 목표 금액 B 이상이 되기를 원한다. 동시에 가능한 한 낮은 상한을 제시하여 손님들의 부담을 줄이려고 한다. 따라서 목표를 달성하는 상한 중 가장 작은 정수 C를 찾아야 한다. 목표 금액과 정확히 같아질 필요는 없으며, 실제 결제 금액의 합이 목표 금액을 초과해도 조건을 만족한다. 주문은 나누거나 합칠 수 없고 행사에서 제외할 수도 없다. 같은 금액의 주문이 여러 개 있더라도 각각 별도로 합산한다. 주어진 범위의 어떤 상한을 선택해도 목표를 달성할 수 없는 경우가 있을 수 있다. 할인 전 주문 금액들과 목표 금액이 주어질 때, 사용할 수 있는 가장 작은 결제 상한을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 B가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 60,000, 0 ≤ B ≤ 1,000,000,000이다.
둘째 줄에 각 주문의 할인 전 결제 금액인 정수 P_1, P_2, ..., P_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ P_i ≤ 9,999이다.

출력

실제 결제 금액의 합을 B 이상으로 만드는 가장 작은 정수 상한 C를 한 줄에 출력한다. C는 0 이상 9,999 이하여야 한다. 조건을 만족하는 C가 없으면 -1을 출력한다.

4 17
2 8 5 9

5

3 20
3 4 5

-1

2 0
7 12

0

출처: Devin.KR 자체 제작