You have an n×nn×n matrix aa. You can rearrange the elements of the matrix in any way. Let m1,m2,…,mnm1,m2,…,mn be the medians of each row in aa after the rearrangement. The goodness of the matrix aa is defined as the minimum median among the medians of all rows i.e min(m1,m2,…,mn)min(m1,m2,…,mn). Naturally, rearranging values also comes with a cost. The cost of rearrangement is defined as m1+m2+⋯+mnm1+m2+⋯+mn.

Median Rearrangement solution codechef

You have an n×nn×n matrix aa. You can rearrange the elements of the matrix in any way. Let m1,m2,,mnm1,m2,…,mn be the medians of each row in aa after the rearrangement. The goodness of the matrix aa is defined as the minimum median among the medians of all rows i.e min(m1,m2,,mn)min(m1,m2,…,mn). Naturally, rearranging values also comes with a cost. The cost of rearrangement is defined as m1+m2++mnm1+m2+⋯+mn.

Find the maximum goodness you can achieve after rearranging a matrix aa such that the cost of rearrangement doesn’t exceed kk or 1−1 if the answer doesn’t exist.

The median of an array aa consisting of nn elements is the n+12th⌈n+12⌉th smallest element of aa. The median of [4,8,6,1][4,8,6,1] is 66 and the median of [1,6,2,4,5][1,6,2,4,5] is 44.

Input Format

  • The first line of the input contains a single integer tt denoting the number of test cases. The description of tt test cases follows.
  • The first line of each test case consists of two space-separated integers nn and kk.
  • nn lines follow, each consisting of nn space-separated integers denoting the matrix aa

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 kk or -1 if the answer doesn’t exist.

Constraints

  • 1t1001≤t≤100
  • 1n10001≤n≤1000
  • 1k10141≤k≤1014
  • 1ai,j1091≤ai,j≤109
  • 1n10001≤∑n≤1000

Subtasks

  • Subtask 1 (20 points): k=1014k=1014

  • Subtask 2 (40 points): 1n701≤∑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

Test case 11: We rearrange the matrix as follows: ⎡⎣⎢⎢⎢⎢11175322315911368163249⎤⎦⎥⎥⎥⎥[11211617313351562432989] . The medians of each row are 11,13,15,911,13,15,9 respectively. The goodness is 99 and the cost is 4848. There are other rearrangements that may yield the same goodness but 99 is the maximum goodness we can get.

Test case 22: The rearranged matrix is: ⎡⎣⎢⎢⎢⎢17211531322486159316139⎤⎦⎥⎥⎥⎥[17383216161132151352499] . The medians of each row are 8,6,15,98,6,15,9 respectively. The goodness is 66 and the cost is 3838. There are other rearrangements that may yield the same goodness but 66 is the maximum goodness we can get.

Test case 33: No matter how we rearrange the elements, the cost is always greater than kk.

Leave a Comment

Your email address will not be published. Required fields are marked *