B'Bernard loves visiting Rudolf, but he is always running late. The problem is that Bernard has to cross the river on a ferry. Rudolf decided to help his friend solve this problem. The river is a grid of n rows and m columns. The intersection of the i -th row and the j -th column contains the number a_{i,j} -- the depth in the corresponding cell. All cells in the first and last columns correspond to the river banks, so the depth for them is 0 . Rudolf can choose the row (i,1), (i,2), ldots, (i,m) and build a bridge over it. In each cell of the row, he can install a support for the bridge. The cost of installing a support in the cell (i,j) is a_{i,j}+1 . Supports must be installed so that the following conditions are met: Building just one bridge is boring. Therefore, Rudolf decided to build k bridges on consecutive rows of the river, that is, to choose some i ( 1 <= i <= n - k + 1 ) and independently build a bridge on each of the rows i, i + 1, ldots, i + k - 1 . Help Rudolf minimize the total cost of installing supports. The first line contains a single integer t (1 <= t <= 10^3) -- the number of test cases. The descriptions of the test cases follow. The first line of each test case contains four integers n , m , k , and d ( 1 <= k <= n <= 100 , 3 <= m <= 2 cdot 10^5 , 1 <= d <= m ) -- the number of rows and columns of the field, the number of bridges, and the maximum distance between supports. Then follow n lines, i -th line contains m positive integers a_{i, j} ( 0 <= a_{i, j} <= 10^6 , a_{i, 1} = a_{i, m} = 0 ) -- the depths of the river cells. It is guaranteed that the sum of n cdot m for all sets of input data does not exceed 2 cdot 10^5 . For each test case, output a single number -- the minimum total cost of supports installation. In the first test case, it is most pro'...