Problem C: Live Schedule

YOKARI TAMURAは全国的に有名なアーティストである。今月YOKARIは D 日間にわたってライブツアーを行う。ツアーのスケジュールの決定においてこの国を C 種類の地域でわける。YOKARIがある地域でライブを行うことにより利益を得られ、これは正の整数で表される。YOKARIは原則として 1 日に最大 1 つまでライブを行う。ただし、ある地域でライブを行った後、隣接する地域でライブを行える場合はその地域で同じ日に再びライブを行うことができる。この条件を満たす限り、地域を移動しながら何度もライブを行うことができる。また、同じ日に同じ地域でライブを 2 度以上行うことはできない。さらに、同じ日に 2 回以上のライブを行う日の数はツアー期間中合計 X 以下でなければならない。

あなたはYOKARIの関係者であり、彼女のライブツアーのスケジュールを仮決めしなくてはならない。どの日にどの地域でライブを行えばもっとも有益だろうか。ただし 1 回のライブごとにYOKARIには非負の整数で表される負担がかかり、ツアー期間中の合計負担は W 以内でなければならない。あなたの仕事は各ライブでYOKARIにかかる負担と期待される利益を読み込み、スケジュールを仮決めして、利益合計の最大値を出力することである。

Input

入力は複数のテストケースからなる。 ひとつのテストケースは以下の形式に従う。

C D W X
E1,1 E1,1 … E1,D
E2,1 E2,1 … E2,D
…
EC,1 EC,2 … EC,D
F1,1 F1,1 … F1,D
F2,1 F2,1 … F2,D
…
FC,1 FC,2 … FC,D

C は地域の種類数、D はツアー期間の長さ、W はこのツアーでYOKARIに許容される負担の合計の最大値、X はツアー期間中にライブを同じ日に 2 度以上行える合計日数の上限である。 E_i,j ( 1 ≤ i ≤ C かつ 1 ≤ j ≤ D ) は地域 i で j 日目にライブを行うことで期待される利益である。E_i,j が 0 のとき地域 i で j 日目にライブを行えないことを示す。 F_i,j ( 1 ≤ i ≤ C かつ 1 ≤ j ≤ D ) は地域 i で j 日目にライブを行うことでYOKARIにかかる負担である。E_i,j が 0 のとき、この値は0である。 地域 i は地域 i + 1 と i - 1 それぞれに隣接する。ただし地域 1 と地域 C ( C > 2 ) は隣接しない。 入力の終わりは、4個の0がそれぞれ一文字の空白で区切られる一行で示される。

Constraints

• 入力はすべて整数
• 1 ≤ C ≤ 15
• 1 ≤ D ≤ 30
• 0 ≤ W ≤ 50
• 0 ≤ X ≤ 5
• 0 ≤ E_i,j ≤ 1,000
• 0 ≤ F_i,j ≤ 10
• テストケースの数は 100 を超えない。

Output

各ケースに付き、スケジュールを仮決めして期待される利益合計の最大値を 1 行に出力せよ。

Sample Input

5 5 10 2
1 1 0 1 1
0 9 1 0 1
1 1 1 9 1
1 1 9 0 1
1 1 1 1 0
1 1 0 1 1
0 9 1 0 1
1 1 1 9 1
1 1 1 0 1
1 1 1 1 0
1 1 10 0
3
7
1 1 5 0
3
6
1 2 10 1
6 7
5 6
2 1 10 1
4
8
3
7
2 1 10 0
4
8
3
7
2 1 5 0
4
8
3
6
0 0 0 0

Sample Output

18
3
0
7
12
8
4

---