Read problem statements in [Mandarin], [Russian], and [Vietnamese] as well.

You have an n \times n matrix a. You can rearrange the elements of the matrix in any way. Let m_{1}, m_{2}, \dots, m_{n} be the medians of each row in a after the rearrangement. The goodness of the matrix a is defined as the minimum median among the medians of all rows i.e \min(m_{1}, m_{2}, \dots, m_{n}). Naturally, rearranging values also comes with a cost. The cost of rearrangement is defined as m_{1} + m_{2} + \dots + m_{n}. 

Find the maximum goodness you can achieve after rearranging a matrix a such that the cost of rearrangement doesn't exceed k or -1 if the answer doesn't exist.

The median of an array a consisting of n elements is the \lceil{\frac{n+1}{2}}\rceil^{th} smallest element of a. The median of [4, 8, 6, 1] is 6 and the median of [1, 6, 2, 4, 5] is 4.

------ Input Format ------ 

- The first line of the input contains a single integer t denoting the number of test cases. The description of t test cases follows.
- The first line of each test case consists of two space-separated integers n and k.
- n lines follow, each consisting of n space-separated integers denoting the matrix a

------ Output Format ------ 

For each test case, print a single line containing one integer - the maximum goodness you can achieve such that the rearrangement cost does not exceed k or -1 if the answer doesn't exist.

------ Constraints ------ 

$1 ≤ t ≤ 100$
$1 ≤ n ≤ 1000$
$1 ≤ k ≤ 10^{14}$
$1 ≤ a_{i, j} ≤ 10^{9}$
$1 ≤ \sum n ≤ 1000$

------ subtasks ------ 

Subtask 1 (20 points): $k = 10^{14}$

Subtask 2 (40 points): $1 ≤ \sum n ≤ 70$

Subtask 3 (40 points): Original constraints

----- Sample Input 1 ------ 
3
4 100
13 2 1 16
15 24 3 3
5 17 9 8
9 6 11 32
4 40
13 2 1 16
15 24 3 3
5 17 9 8
9 6 11 32
3 1
3 4 2
5 7 9
2 1 1

----- Sample Output 1 ------ 
9
6
-1
----- explanation 1 ------ 
Test case $1$:  We rearrange the matrix as follows:
$\begin{bmatrix}
11 & 2 & 1 & 16\\
17 & 3 & 13 & 3\\
5 & 15 & 6 & 24\\
32& 9 & 8 & 9
\end{bmatrix}$
. The medians of each row are $11, 13, 15, 9$ respectively. The goodness is $9$ and the cost is $48$. There are other rearrangements that may yield the same goodness but $9$ is the maximum goodness we can get. 

Test case $2$:  The rearranged matrix is:
$\begin{bmatrix}
17 & 3 & 8 & 3\\
2 & 1 & 6 & 16\\
11& 32 & 15 & 13\\
5 & 24 & 9 & 9
\end{bmatrix}$
. The medians of each row are $8, 6, 15, 9$ respectively. The goodness is $6$ and the cost is $38$. There are other rearrangements that may yield the same goodness but $6$ is the maximum goodness we can get. 

Test case $3$:  No matter how we rearrange the elements, the cost is always greater than $k$.

Difficulty: VERY_HARD
Tags: Sorting

Range queries

Complete search

Greedy algorithms

Mathematics

Data structures
Skill types: Sorting

Range queries

Greedy algorithms

Complete search

Data structures

Starter code:

Solutions:
for z in range(int(input())):
	(n, k) = map(int, input().split())
	A = []
	for i in range(n):
		A += list(map(int, input().split()))
	A.sort()
	leftcount = int(n / 2)
	rightcount = n - leftcount - 1
	righttotal = rightcount * n
	rmax = n * n - righttotal - 1
	ans = -1
	start = leftcount
	end = n * n - righttotal - (n - 1) - 1
	while start <= end:
		mid = start + int((end - start) / 2)
		x = 0
		y = mid
		vis = []
		for i in range(n * n):
			vis.append(0)
		tot = 0
		cnt = 0
		sums = 0
		while tot != n:
			if cnt == leftcount:
				if vis[y] == 0:
					sums += A[y]
					vis[y] = 1
					y += 1
					tot += 1
					cnt = 0
				else:
					y += 1
			elif vis[x] == 0:
				vis[x] = 1
				x += 1
				cnt += 1
			else:
				x += 1
		if sums <= k:
			ans = mid
			start = mid + 1
		else:
			end = mid - 1
	if ans == -1:
		print(-1)
	else:
		print(A[ans])


t = int(input())
for _ in range(t):
	args = [int(x) for x in input().split()]
	(n, k) = (args[0], args[1])
	nums = []
	for __ in range(n):
		nums.extend([int(x) for x in input().split()])
	nums.sort()
	min_goodness = 0
	for i in range(n):
		min_goodness += nums[(i + 1) * (n // 2)]
	if min_goodness > k:
		print(-1)
		continue
	(lo, hi) = (n // 2, n * n - 1)
	goodness = -1
	while lo <= hi:
		mid = (lo + hi) // 2
		taken = 0
		rlim = n * n
		less = mid
		i = mid
		cost = 0
		while taken <= n and i < rlim:
			if less >= n // 2:
				cost += nums[i]
				less -= n // 2
				rlim -= n - n // 2 - 1
				if rlim <= i:
					break
				taken += 1
			else:
				less += 1
			i += 1
		if taken == n and cost <= k:
			lo = mid + 1
			goodness = nums[mid]
		else:
			hi = mid - 1
	print(goodness)


try:
	for t in range(int(input())):
		(n, k) = map(int, input().split())
		a = []
		for i in range(n):
			r = list(input().split())
			for i in range(n):
				r[i] = int(r[i])
			for element in r:
				a.append(element)
			r = []
		a.sort()

		def solve(a, m):
			summ = a[m]
			d = n // 2
			for i in range(2, n + 1):
				summ += a[max(m + i - 1, d + (i - 1) * (d + 1))]
			return summ
		l = n // 2
		r = n * n - n - n * (n // 2 - (n + 1) % 2)
		while r - l > 1:
			m = (l + r) // 2
			if solve(a, m) > k:
				r = m - 1
			else:
				l = m
		if solve(a, r) <= k:
			print(a[r])
		elif solve(a, l) <= k:
			print(a[l])
		else:
			print(-1)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mat = []
	for i in range(n):
		temp = list(map(int, input().split()))
		for j in temp:
			mat.append(j)
	mat.sort()
	med = n // 2
	medians = []
	l = 0
	while l < n:
		medians.append(med)
		med += n // 2 + 1
		l += 1
	postfix = [0] * n
	summ = 0
	for i in range(n - 1, -1, -1):
		summ += mat[medians[i]]
		postfix[i] = summ
	if postfix[0] > k:
		print(-1)
	else:
		ans = mat[medians[0]]
		t = 0
		for i in range(1, n):
			low = t + 1
			high = medians[i] - i
			if high < low:
				low = high
			t = high
			while low <= high:
				mid = (low + high) // 2
				temp = postfix[i]
				for j in range(i):
					temp += mat[mid + j]
				if temp > k:
					high = mid - 1
				else:
					if mat[mid] > ans:
						ans = mat[mid]
					low = mid + 1
		print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = []
	for _ in range(n):
		l1 = l1 + list(map(int, input().split()))
	l1.sort()
	l = ini = math.ceil((n + 1) / 2) - 1
	h = ini * n
	good = -1
	while l <= h:
		mid = (l + h) // 2
		if mid == ini * n:
			if sum(l1[mid:mid + n]) <= k:
				good = max(good, l1[mid])
				l = mid + 1
			else:
				h = mid - 1
		else:
			short = ini * n - mid
			check_tot = 0
			e = mid + (math.floor(mid / ini) - 1)
			for j in range(mid, e + 1):
				check_tot += l1[j]
			rem = mid - ini * math.floor(mid / ini)
			check_tot += l1[e + ini - rem + 1] if rem != 0 else 0
			start = e + 2 * ini - rem + 2 if rem != 0 else e + ini + 1
			for j in range(start, start + (n - math.ceil(mid / ini) - 1) * (ini + 1) + 1, ini + 1):
				check_tot += l1[j]
			if check_tot <= k:
				good = max(good, l1[mid])
				l = mid + 1
			else:
				h = mid - 1
	print(good)


import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.extend(list(map(int, input().split())))
	arr = sorted(arr)
	ans = n * int(n / 2)
	sum = 0
	for i in range(ans, ans + n):
		sum += arr[i]
	while sum > k:
		if ans <= 1:
			break
		fix = int((ans - 1) / int(n / 2)) - 1
		if fix < 0:
			break
		sum += arr[ans - 1] - arr[ans + fix]
		ans -= 1
	if sum > k:
		print(-1)
	else:
		print(arr[ans])


from collections import defaultdict
from sys import stdin, stdout, setrecursionlimit
import math
(readline, writeline) = (stdin.readline, stdout.write)
setrecursionlimit(100005)
for _ in range(int(readline())):
	lst = []
	(n, k) = map(int, readline().split())
	for i in range(n):
		lst += list(map(int, readline().split()))
	lst.sort()
	ans = -1
	l = n // 2
	r = n * l
	while l <= r:
		mid = (l + r) // 2
		(tot, cnt, add, x) = (0, 0, 0, 0)
		visited = [0] * n ** 2
		tar = mid
		while tot != n:
			if cnt == n // 2:
				if not visited[tar]:
					visited[tar] = 1
					tot += 1
					add += lst[tar]
					cnt = 0
				tar += 1
			else:
				if not visited[x]:
					visited[x] = 1
					cnt += 1
				x += 1
		if add > k:
			r = mid - 1
		else:
			ans = lst[mid]
			l = mid + 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		t = list(map(int, input().split()))
		a += t
	a.sort()
	r = n * (n // 2)
	l = n // 2
	ans = -1
	while r >= l:
		mid = (l + r) // 2
		i = mid
		v = 1
		sm = a[mid]
		left = mid - n // 2
		while v != n:
			if left >= n // 2:
				i += 1
				left -= n // 2
			else:
				i += n // 2 - left + 1
				left = 0
			sm += a[i]
			v += 1
		if sm <= k:
			l = mid + 1
			ans = mid
		else:
			r = mid - 1
	if ans == -1:
		print(-1)
	else:
		print(a[ans])


for T in range(int(input())):
	(n, k) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append([int(i) for i in input().split()])
	ar = []
	for i in range(n):
		for j in range(n):
			ar.append(arr[i][j])
	ar.sort()
	leftcount = n // 2
	rightcount = n - leftcount - 1
	righttotal = rightcount * n
	ans = -1
	l = leftcount
	r = n * n - righttotal - (n - 1) - 1
	while l <= r:
		mid = (l + r) // 2
		sum = 0
		cnt = 0
		tot = 0
		x = 0
		y = mid
		vis = [0] * (n * n)
		while tot != n:
			if cnt == leftcount:
				if vis[y] == 0:
					vis[y] = 1
					sum += ar[y]
					y += 1
					tot += 1
					cnt = 0
				else:
					y += 1
			elif vis[x] == 0:
				vis[x] = 1
				x += 1
				cnt += 1
			else:
				x += 1
		if sum <= k:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	if ans == -1:
		print(ans)
	else:
		print(ar[ans])


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array
import collections

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
from math import ceil
from itertools import permutations, combinations
from collections import Counter
for _ in range(*maps()):
	(n, k) = maps()
	A = []
	[A.extend(maps()) for i in range(n)]
	A.sort()
	debug('A', A)
	(N, mi_cost, i, j) = (n * n, 0, n // 2, 0)
	while j < n:
		mi_cost += A[i]
		i += n // 2 + 1
		j += 1
	if mi_cost > k:
		print(-1)
		continue
	(lo, hi) = (n // 2, N - 1)
	while lo < hi:
		mid = (lo + hi + 1) // 2
		taken = 0
		cost = 0
		rleft = N
		i = mid
		smallest = mid
		while taken < n and i < N:
			if i >= rleft:
				break
			if smallest >= n // 2:
				taken += 1
				cost += A[i]
				rleft -= n - n // 2 - 1
				smallest -= n // 2
				if i >= rleft:
					cost = k + 1
					break
			else:
				smallest += 1
			i += 1
		if taken < n:
			cost = k + 1
		if cost <= k:
			lo = mid
		else:
			hi = mid - 1
	print(A[lo])


from math import ceil

def ii():
	return int(input())

def imi():
	return map(int, input().split())

def il():
	return list(map(int, input().split()))
inf = 10 ** 30

def max_cost(i, li, n, m):
	if i < m:
		return inf
	ar = [1] * (n * n + 1)
	j = 1
	s = 0
	lt = i
	for _ in range(n):
		if i > n * n:
			return inf
		c = 0
		while c < m - 1:
			if ar[j] >= 0:
				ar[j] = -1
				c += 1
			j += 1
			if j > n * n:
				break
		while ar[i] == -1:
			i += 1
			if i > n * n:
				return inf
		s += li[i]
		ar[i] = -1
		lt = i
	if n * n - lt < n * (n - m):
		return inf
	return s
t = int(input())
for _ in range(t):
	(n, k) = imi()
	li = []
	for i in range(n):
		li += il()
	li.sort()
	li = [0] + li
	m = ceil((n + 1) / 2)
	l = m
	r = n * n
	ans = -1
	while l < r:
		i = (l + r) // 2
		if max_cost(i, li, n, m) <= k:
			ans = max(li[i], ans)
			l = i + 1
		else:
			r = i - 1
	if max_cost(l, li, n, m) <= k:
		ans = li[l]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	median = n // 2
	x = median - 1
	num = n * median
	flag = 0
	a = []
	for i in range(n):
		a.extend(map(int, input().split()))
	a.sort()
	s = sum(a[num:num + n])
	if s <= k:
		print(min(a[num:num + n]))
	else:
		ref = a[median:num].copy()
		new_lst = a[num:num + n].copy()
		new_lst.reverse()
		while len(ref):
			x += 1
			new_lst.append(ref[-1])
			new_lst.pop(x // median)
			if k >= sum(new_lst):
				print(ref[-1])
				flag = 1
				break
			else:
				ref.pop(-1)
		if not flag:
			print(-1)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [0]
	arr2D = []
	for i in range(n):
		arr2D.append(list(map(int, input().split())))
	for i in range(n):
		for j in range(n):
			arr.append(arr2D[i][j])
	arr.sort()
	total = n * n
	start = int(math.ceil((n + 1) / 2))
	end = (n - start) * n
	mini = 0
	medianCollection = []
	count = 0
	for i in range(start, total - end + 1):
		medianCollection.append(arr[i])
		count += 1
		if count % start == 1:
			mini += arr[i]
	if k < mini:
		print(-1)
	else:
		prefixSum = [0 for i in range(count + 1)]
		prefixSum[0] = medianCollection[0]
		for i in range(1, count):
			prefixSum[i] = prefixSum[i - 1] + medianCollection[i]
		wsum = 0
		mins = 9999999999999999999
		for i in range(count - 1, count - n - 1, -1):
			wsum += medianCollection[i]
			mins = min(mins, medianCollection[i])
		if wsum <= k:
			print(mins)
			continue
		else:
			lsum = 0
			loop = n
			ansYes = True
			moves = count - 1
			while moves >= 0:
				if moves % start == 0:
					lsum += medianCollection[moves]
					loop = loop - 1
				wsum = lsum + prefixSum[moves] - prefixSum[moves - loop]
				if wsum <= k:
					ansYes = False
					print(mins)
					break
				mins = min(mins, medianCollection[moves - loop])
				moves = moves - 1
			if ansYes:
				print(-1)


import math
from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, gcd, log
import bisect
import sys
import random
import heapq

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def possible(ind, n, k, l):
	max_ind = n * n // 2 + n - 1
	mid = n // 2
	counter = n
	val = ind // mid
	sm = sum(l[ind:ind + val])
	counter -= ind // mid
	if counter <= 0 and sm <= k:
		return True
	remain = ind % mid
	break_cond = n * n
	for i in range(ind + val, n * n):
		if remain == mid:
			sm += l[i]
			counter -= 1
			remain = 0
		else:
			remain += 1
		if counter == 0:
			break_cond = i
			break
	if break_cond <= max_ind and sm <= k:
		return True
	return False

def main():
	for _ in range(int(input())):
		(n, k) = get_ints()
		l = []
		for _ in range(n):
			tmp = get_array()
			l.extend(tmp)
		l.sort()
		if n == 1:
			if l[0] > k:
				print(-1)
			else:
				print(l[0])
			continue
		ans = -1
		left = n // 2
		right = n * n // 2
		while right >= left:
			mid = (left + right) // 2
			if possible(mid, n, k, l):
				ans = l[mid]
				left = mid + 1
			else:
				right = mid - 1
		print(ans)
main()


from math import ceil, log2, floor, sqrt, gcd
from collections import defaultdict, deque
from os import P_WAIT
from collections import defaultdict
from ntpath import realpath
import sys
import os.path
sys.setrecursionlimit(200000)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r+')
	sys.stdout = open('output.txt', 'w')

def MI():
	return map(int, input().split())
mod = 10 ** 9 + 7

def solve(testcase):
	(n, k) = MI()
	a = []
	for i in range(n):
		l = list(MI())
		for j in l:
			a.append(j)
	a.sort()
	mid = n // 2
	minn = 0
	d = n - mid - 1
	max_mid = n ** 2 - n * d - n
	st = mid
	en = max_mid
	ans = -1
	while st <= en and st >= 0 and (en < n ** 2):
		m = st + en >> 1
		cost = 0
		pre = m
		i = m
		c = n
		while i < n ** 2:
			cost += a[i]
			pre -= mid
			if pre < mid:
				i += mid - max(0, pre) + 1
				pre = mid
			else:
				i += 1
			c -= 1
			if c == 0:
				break
		if cost <= k:
			st = m + 1
			ans = max(a[m], ans)
		else:
			en = m - 1
	print(ans)
t = int(input())
for _ in range(t):
	solve(_ + 1)


import math
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	M = []
	for i in range(N):
		M.append(list(map(int, input().split())))
	A = []
	for i in range(N):
		A.extend(M[i])
	A.sort()
	a = N * N - (N - math.ceil((N + 1) / 2)) * N - N
	c = 0
	h = N
	l = 0
	for i in range(a, a + N):
		l += A[i]
	a -= 1
	while l > K and a >= math.ceil((N + 1) / 2) - 1:
		if c == 0:
			h -= 1
		l += A[a] - A[a + h]
		a -= 1
		c = (c + 1) % (math.ceil((N + 1) / 2) - 1)
	if l > K:
		print(-1)
	else:
		print(A[a + 1])


def find(point):
	(cnt, sum) = (0, 0)
	temp = point
	while cnt != n:
		if temp >= n // 2:
			sum = sum + l[point]
			temp = temp - n // 2
		elif temp:
			sum = sum + l[point + (n // 2 - temp)]
			point = point + (n // 2 - temp)
			temp = 0
		else:
			sum = sum + l[point + n // 2]
			point = point + n // 2
		point = point + 1
		cnt = cnt + 1
	return sum
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for _ in range(n):
		l.extend(list(map(int, input().split())))
	l.sort()
	ans = -1
	low = n // 2
	high = n * (n // 2)
	while low <= high:
		mid = (low + high) // 2
		temp = find(mid)
		if temp <= k:
			ans = l[mid]
			low = mid + 1
		else:
			high = mid - 1
	print(ans)


t = int(input())
for i in range(t):
	t -= 1
	(n, k) = map(int, input().split())
	r = []
	for i in range(n):
		a = list(map(int, input().split()))
		r.extend(a)
	r.sort()
	re = n * (n // 2)
	z = sum(r[re:re + n])
	if z <= k:
		print(r[re])
	else:
		fl = 0
		cur = z
		lastpos = re + n - 1
		firstpos = re
		for i in range(n - 1):
			for j in range(n // 2):
				cur -= r[lastpos - 1]
				lastpos -= 1
				cur += r[firstpos - 1]
				firstpos -= 1
				if cur <= k:
					fl = 1
					print(r[firstpos])
					break
			lastpos -= 1
			if fl:
				break
		if fl == 0:
			print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	for _ in range(n):
		a.extend(map(int, input().split()))
	a.sort()
	med = n // 2
	cost_minim = sum((a[med + i * (med + 1)] for i in range(n)))
	if cost_minim > k:
		print(-1)
	else:
		med_minim = a[n * med:n * (med + 1)]
		cost_med_minim = sum(med_minim)
		minim = med_minim[0]
		if cost_med_minim <= k:
			print(minim)
		else:
			num = a[:n * (med + 1)][::-1]
			s = sum(num[:n])
			(pos, right) = (0, n)
			while s > k:
				if pos % (med + 1) == 0:
					pos += 1
					right -= 1
				s += num[pos + right] - num[pos]
				pos += 1
			print(num[pos - 1 + right])


import sys
import math
import random
import heapq
input = sys.stdin.readline

def pow(a, n):
	if n == 0:
		return 1
	x = pow(a, n // 2)
	if n % 2 == 0:
		return x * x
	else:
		return x * x * a

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def bs(arr, le, ri):
	l = 0
	arr.sort()
	r = len(arr) - 1
	ans = 10000000
	while l <= r:
		m = (l + r) // 2
		if arr[m] >= le and arr[m] <= ri:
			ans = arr[m]
			r = m - 1
		elif arr[m] < le:
			l = m + 1
		else:
			r = m - 1
	return ans
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(n - 1):
		l.extend(list(map(int, input().split())))
	l.sort(reverse=True)
	x = (n // 2 + n % 2 - 1) * n
	te = x
	m = 0
	for i in range(n):
		m += l[x]
		x += 1
	if m <= k:
		print(l[x - 1])
	else:
		y = n // 2 + 1
		while m > k and n * n - 1 - x >= n // 2:
			if (n * n - te) % y != 0:
				m -= l[te]
				m += l[x]
				x += 1
				te += 1
			else:
				te += 1
		if m <= k:
			print(l[x - 1])
		else:
			print(-1)
	t -= 1