사람들이 다닐 수 있는 대학은 많지만 소들이 다닐 대학은 없어 여러마리의 소들이 모여 대학을 하나 만들기로 했다. 이름하여 "엄매 대"
똑똑한 소들을 모집하기 위하여 입학시험을 보기로 했다. 이름하여 CSAT(Cow Scholastic Aptitude Test)
엄매대학은 등록금이 매우 비싸다. 모든 소들은 이 등록금을 댈 수가 없다. 사실 대부분의 소들은 장학금이 필요하다. (0 <= 장학금(aid) <=100,000)
하지만 정부에서는 이 장학금을 지원 할 수가 없어 대학 자체적으로 해야 한다.( 0 <= 지원금액(F) <= 2,000,000,000).
엄매대학은 지원자 C (N <= C <= 100,000) 중에서 홀수 N ( 1 <= N <= 19,999) 명을 뽑는다.
엄매대의 입학처는 교육의 기회를 최대화 하기 위하여 정확히 N 마리의 소들이 입학 하기를 원한다. 또한 CSAT 시험의 중위수가 가능한 높게.
중위 수는 정렬된 홀수 개에서 중간 수를 의미한다는 것을 상기하라. 예를 들어,{3, 8, 9, 7, 5} 에서 중위수는 7 이고 중위 수 아래에 있는 2 개의 수가 있다.
소들의 입학성적,필요한 장학금,입학인원,지원가능한 금액이 주어질 때 중위수를 최상으로 하기 위한 중위수를 구하는게 문제이다.
입력 3 5 70 30 25 50 21 20 20 5 18 35 30 출력 35
출처: USACO 2004 March Green