아무도 받을 수 없는 상품
면접 대비시간 제한1.5초메모리 제한512 MB
두 상품의 가격 합이 X를 초과하는 조합이 없는 상품 부분집합의 최대 크기를 출력한다.
문제
새로 연 가게, Alternative Paramedicine and Cwakhsahlvereigh를 위한 부티크의 화려한 개업식이 끝난 뒤, 아쉽게도 매출이 기대만큼 오르지 않았다는 사실을 알게 되었다. 이를 만회하기 위해 특별 할인 행사를 열기로 한다. 가게에서 파는 n개의 물건 가운데 일부를 행사 참여 물건으로 표시하고, 사람들이 이 물건 중 정확히 두 개를 사면서 그 가격의 합이 X유로보다 엄격하게 크면, 무료로 유니콘 뿔을 하나 준다.
최근에 모든 유니콘 뿔이 사실은 일각고래 엄니라는 것을 알게 되었으므로, 참여 물건을 정할 때 아무도 뿔을 받지 못하도록 속임수를 쓰기로 한다.
아무도 의심하지 않게 하려면, 행사 참여 물건을 최대한 많이 표시하고 싶다.
입력
- 첫째 줄에 정수 두 개가 주어진다. n은 가게에서 파는 물건의 수(1 ≤ n ≤ 105), X는 문제에서 정한 최소 금액(1 ≤ X ≤ 109)이다.
- 둘째 줄에 n개의 양의 정수가 주어지며, 각 값은 109 이하다. 이는 가게 물건의 가격이다.
출력
아무도 실제로 뿔을 받을 수 없으면서 특별 할인 행사의 참여 물건으로 표시할 수 있는 물건의 최대 개수를 출력한다.