소 대학 timer 1s memory 64MB

똑똑한 소 베시는 사람들을 위한 대학은 많지만 소들을 위한 대학은 없다는 것을 확인했다. 이 문제를 해결하기 위해서 "소 대학"을 세우기로 했다. 평균 이하의 소들을 뽑지 않기 위해서 설립자들은 아주 정교한 소 수학능력 시험(CSAT)을 개발하였다. 이 시험의 점수는 1 ... 2,000,000,000 범위로 나타난다.

소 대학의 학비는 매우 비싸다. 때문에 각 소들은 학자금 대출을 특정 금액 받아야 한다(0≤A≤100,000). 정부가 장학금을 지원하지 않기 때문에 학교 재정으로 충당해야 한다. 학교 재정상 F(0≤F≤2,000,000,000)만큼 지원이 가능하다. 이번에 C명의 소들이 지원하였는데 이중에서 N명을 선발해야 한다. N(1≤N≤19,999)은 홀수이며, C(N≤C≤100,000).

베시는 한정된 재정내에서 N마리를 선발해야 하며 선발된 소들의 점수들의 중간값이 최대가 되게 하고 싶다. 소들은 홀수 마리 선발되며 예를 들어 뽑힌 소들의 점수 {3, 8, 9, 7, 5}라면 중간 값은 7이 된다.