DreamChaser is an employee at Baozii Corporations. As a considerate boss, Baozii provides a daily transportation allowance of $$$k$$$ dollars for each employee before they go home after work. To complete an ongoing project, DreamChaser must work overtime for $$$n$$$ consecutive days. Fortunately, the company offers $$$m$$$ shuttle services each day to send employees home.
The cost and arrival time of each shuttle are represented by two matrices, $$$c$$$ and $$$t$$$. Specifically, $$$c_{i,j}$$$ represents the cost of the $$$j$$$-th shuttle on the $$$i$$$-th day, and $$$t_{i,j}$$$ represents the time at which the $$$j$$$-th shuttle on the $$$i$$$-th day arrives at DreamChaser's home.
DreamChaser plans to use only the transportation allowance provided by the company to take the shuttles. Note that any unused transportation allowance from previous days can be carried over to subsequent days, but at no point can DreamChaser's funds become negative. Additionally, DreamChaser must return home every day.
For a time $$$s$$$, if DreamChaser can return home no later than $$$s$$$, then $$$s$$$ is considered good. Find the smallest good $$$s$$$, or report it does not exist.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.
The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le m \le 1000$$$, $$$1 \le k \le 10^9$$$) — the number of days of working overtime, and the number of shuttle services provided.
The following $$$n$$$ lines describe the matrix $$$c$$$, where the $$$i$$$-th line contains $$$m$$$ integers $$$c_{i,1},c_{i,2},\ldots,c_{i,m}$$$ ($$$1 \le c_{i,j} \le 10^9$$$).
The following $$$n$$$ lines describe the matrix $$$t$$$, where the $$$i$$$-th line contains $$$m$$$ integers $$$t_{i,1},t_{i,2},\ldots,t_{i,m}$$$ ($$$1 \le t_{i,j} \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases does not exceed $$$1000$$$.
For each test case, if the transportation allowance is enough, output the smallest good $$$s$$$. Otherwise, output $$$-1$$$.
13 2 33 42 33 41 13 23 4
3
