有一条 n×m 的河。第 i 行第 j 列的深度为 ai,j。保证 ai,1=ai,m=0（即第1列和最后1列均为 0）。
如果在第 i 行第 j 列安置桥墩，所需代价为 ai,j+1。
你需要选择连续的 k 行，每行都要架起若干个桥墩，并满足以下条件：

1. 每行的第 1 列必须架桥墩；
2. 每行的第 m 列必须架桥墩；
3. 每行的相邻两个桥墩的距离不超过 d。其中 (i,j1)(i,j1) 和 (i,j2)(i,j2) 之间的距离为 ∣j1−j2∣−1。

求最小代价和。

第一行包含4个整数，分别是 n, m, k, d，n和m表示河的长和宽，k表示选择的k行桥墩，d表示某一行中两个桥墩的最大距离。
 ( 1 ≤ k ≤ n ≤ 100 , 3 ≤ m ≤ 2×10⁵ , 1 ≤ d ≤ m ) 
接下来共 n 行 m 列，表示在第 i 行第 j 列安置桥墩的代价。( 0 ≤ ai,j ≤10⁶ , ai,1 = ai,m = 0 ) 
保证所有的代价总和不超过2×10⁹

输出一个整数，表示过河时最小安置桥墩的代价。