#P1619D. New Year's Problem
New Year's Problem
No submission language available for this problem.
Description
Vlad has friends, for each of whom he wants to buy one gift for the New Year.
There are shops in the city, in each of which he can buy a gift for any of his friends. If the -th friend () receives a gift bought in the shop with the number (), then the friend receives units of joy. The rectangular table is given in the input.
Vlad has time to visit at most shops (where is the number of friends). He chooses which shops he will visit and for which friends he will buy gifts in each of them.
Let the -th friend receive units of joy from Vlad's gift. Let's find the value . Vlad's goal is to buy gifts so that the value of is as large as possible. In other words, Vlad wants to maximize the minimum of the joys of his friends.
For example, let , . Let the joy from the gifts that we can buy in the first shop: , , in the second shop: , .
Then it is enough for Vlad to go only to the second shop and buy a gift for the first friend, bringing joy , and for the second — bringing joy . In this case, the value will be equal to
Help Vlad choose gifts for his friends so that the value of is as high as possible. Please note that each friend must receive one gift. Vlad can visit at most shops (where is the number of friends). In the shop, he can buy any number of gifts.
The first line of the input contains an integer () — the number of test cases in the input.
An empty line is written before each test case. Then there is a line containing integers and (, ) separated by a space — the number of shops and the number of friends, where is the product of and .
Then lines follow, each containing numbers. The number in the -th row of the -th column () is the joy of the product intended for friend number in shop number .
It is guaranteed that the sum of the values over all test cases in the test does not exceed .
Print lines, each line must contain the answer to the corresponding test case — the maximum possible value of , where is the minimum of the joys from a gift for all of Vlad's friends.
Input
The first line of the input contains an integer () — the number of test cases in the input.
An empty line is written before each test case. Then there is a line containing integers and (, ) separated by a space — the number of shops and the number of friends, where is the product of and .
Then lines follow, each containing numbers. The number in the -th row of the -th column () is the joy of the product intended for friend number in shop number .
It is guaranteed that the sum of the values over all test cases in the test does not exceed .
Output
Print lines, each line must contain the answer to the corresponding test case — the maximum possible value of , where is the minimum of the joys from a gift for all of Vlad's friends.