题号：NC25718
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
In recent time, Hua Nong brothers' bamboo rat videos go viral and they have been Internet celebrities ever since then. As an investor, Boss Niu decides to build a breeding base to culture bamboo rats.
The breeding base can be described as a 
matrix, each cell of which contains a bamboo rat. Generally, every bamboo rat has a weight w.
Today, Brother Wang comes to visit Boss Niu. Thus Boss Niu will select exactly k pretty bamboo rats to roast. In order not to make breeding base look so empty, Boss Niu can't select two adjacent bamboo rats. That is to say, if there are two bamboo rats sharing the same edge, he just can select one at most. Among k bamboo rats he selects, Boss Niu wants the weight of the lightest bamboo rat maximum. Please tell him the maximum weight of the lightest one.
输入描述:
The first line contains an integer number T, the number of test cases.
For each test case:
The first line contains three integers n, m, k(), the size of matrix and the number Boss Niu need to select.
The following n lines, each contains m integers(
), the weight of bamboo rats.
输出描述:
For each test case print the answer.