School Inspection

G. School Inspection

No Submission Yet

Problem Statement

Lexington high school can be modeled as a row of \(N\) bathrooms, each has a boy room with cleanliness value \(a_i\) and girl room with cleanliness value \(b_i\).

One day, the health inspector suddenly came to town! Since the health report is closely tied to how much funding the school receives, Principal Snehpets wants to maximize the cleanliness as much as possible. To do so, he may swap the bathroom gender signs of the girl bathroom and the boy bathroom (Essentially swapping the values of \(a_i\) and \(b_i\)). However, because the inspector's visit is so sudden, Snehpets only has time to swap the signs for at most \(K\) groups of bathrooms! A set of bathrooms are considered to be a group if they form a nonempty contiguous subarray.

The cleanliness of the school is defined as the minimum between the median cleanliness of all girl's bathrooms and the median cleanliness of all boy's bathrooms. The median of a multiset with size \(n\) is defined as the \(\lceil\frac{n}{2}\rceil\) th smallest element. Help Principal Snehpets find the maximum possible cleanliness for the school!

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb


\(N,K \leq 10^5\)
\(1 \leq a_i,b_i \leq 10^9\)

Input Format

The first line contains two integers \(N\) and \(K\).
The second line contains \(N\) integers. The \(i\)th integer is the \(i\)th boy's bathroom cleanliness, \(a_i\).
The third line contains \(N\) integers, the \(i\)th integer is the \(i\)th girl's bathroom cleanliness, \(b_i\).

Output Format

Output the maximum achievable cleanliness value of the school.

Sample Input

6 2
10 6 9 7 9 6
6 4 1 6 4 5

Sample Output


Sample Explanation

You actually only need to swap one group of bathrooms \([2,3]\). Subequently, both girl's and boy's bathrooms have a median cleanliness of \(6\). Taking the minimum gives an overall cleanliness of the school \(6\).

Credit: CodeTiger

Contact Us
LIT Discord Server