P4952 [USACO04MAR] Financial Aid

Humans can choose from many colleges, but cows have nowhere to go to school. To solve this problem, Bessie and her friends founded a cow university called Moo Moo University. In order to select outstanding students, they invented a Cow Scholastic Ability Test (CSAT). The scores of this test are extremely precise: each cow’s score can be represented by an integer between $0$ and $2×10^9$, and it is guaranteed that no two cows have the same score. Tuition at Moo Moo University is very expensive, and the cows cannot afford it, so they each apply for financial aid. The government does not provide scholarships for cows; all funding must be paid from the school’s limited financial aid fund (let the total fund be $F$). Moo Moo University has $N$ dorm rooms. Since $N$ is an odd number, Bessie can accept applications from only $N$ cows, and she swears she will not admit fewer than $N$ cows. In addition, she wants the freshmen to have excellent CSAT performance, and she measures the overall level by the median. The median is the score in the exact middle after sorting. For example, the median of 3, 8, 9, 7, 5 is 7. This year, a total of $C$ cows apply. Given each cow’s CSAT score and the amount of financial aid requested, as well as the total amount the school can sponsor, determine which cows Bessie should accept so that the median score is as large as possible.

Line 1: Three integers separated by spaces: $N$, $C$, and $F$. $1 ≤ N ≤ 19999$, $N ≤ C ≤ 10^5$, $0 ≤ F ≤ 2 × 10^9$. Lines 2 to $C + 1$: Each line contains two integers separated by a space. The first number is the cow’s CSAT score, and the second number is the amount of financial aid this cow requires, $Q_i$. $0 ≤ Q_i ≤ 10^5$.

Line 1: One integer, the maximum median Bessie can achieve. If the current fund is not enough to support any $N$ cows, output $-1$.

Bessie accepts cows with CSAT scores 5, 35, and 50. The median is 35, and the total financial aid required is $18 + 30 + 21 = 69$. Translated by ChatGPT 5