Aizu Buried Treasure

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem I: 会津の埋蔵金

会津には古くから伝わる埋蔵金の伝説があります。一攫千金を目指すじゅん君は、遂に埋蔵金が埋まっている場所を突き止めました。しかし、じゅん君は埋蔵金発掘のための十分な資金は持っておらず、無駄な作業は控えたいところです。幸いにして、埋蔵金が埋まっている深さ、掘り進める地層の状態は分かっているので、綿密に計画を立てれば最小費用で埋蔵金まで到達できます。しかし、じゅん君はこのような計画をするのは苦手で、相棒のあなたに手助けを求めてきました。あなたはじゅん君を助けるために、 地層の状態を読み取って埋蔵金の埋まっている深さまで最小費用で到達するルートを算出するプログラムを作成しなくてはなりません。

  • 地層の状態は 2 次元格子状に配置されたセルで表わされ、各セルの位置は座標(x,y)で表されます。左上を(1,1)とし、x 座標は右に行くにつれて大きくなり、y 座標は下に深くなるにつれて大きくなるものとします。じゅん君は y 座標の一番小さいセルのうち一つを選んでそこから掘り始め、y 座標の一番大きいセルの一つまで掘り進めます。セルの状態は 2 パターンあり、
    1. 土の詰まったセル。掘るのに、セルごとに決められた費用がかかる。
    2. 酸素のたまったセル。掘る必要はなく、セルごとに決まった量の酸素を補給できる。一度酸素を補給したセルの酸素はなくなり、再度の補給はできない。また、このセルに辿りついたら必ず酸素の補給をしなければならない。
    となっています。
  • あるセルから掘ることができるのは左右と下方向のセルのみです。
  • 一度掘ったセルを左右に移動することはできますが、上に移動することはできません。
  • 発掘にあたっては、酸素ボンベを携帯しなければなりません。酸素ボンベの残量が 0 になった瞬間、移動も発掘も酸素の補給もできなくなります。残量はセルを移動するたびに 1 減ります。酸素ボンベの残量が 0 で埋蔵金の埋まっている深さまで到達しても、到達したとみなされません。また、酸素のたまったセルでは酸素を補給することができますが、容量を超えた分は廃棄されます。

地層のサイズ(横 W,縦 H) 、じゅん君の発掘費用 f、酸素ボンベの容量 m、初期状態で持っている酸素の量 o、地層の情報を入力とし、一番深いセルまでたどりつくための最小費用を出力するプログラムを作成してください。ただし、W は 3 以上 10 以下の整数、H は 3 以上 10 以下の整数、f は 1 以上 10000以下の整数、m は 3 以上 50 以下の整数、o は m 以下の整数とします。また、酸素のたまったセルは 50 箇所以内だとします。なお、最小費用が発掘費用を超えてしまう場合や、どのように掘り進めても埋蔵金にたどりつけない場合は“NA”と出力してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。 各データセットは以下のとおりです。

1 行目 横 W 縦 H(整数 整数;半角空白区切り)
2 行目 発掘費用 f 酸素ボンベの容量 m 初期状態の酸素の量 o(整数 整数 整数;半角空白区切り)
3 行目 地層の 1 行目の情報 c1 c2 ... cW(それぞれ整数;半角空白区切り)
各 ci は、座標(i,1)に対するセルの情報で、意味は以下の通り
負の値:土の詰まったセルで、値は費用を表す
正の値:酸素のたまったセルで、値は酸素の量を表す
4 行目 地層の 2 行目の情報
:
H+2 行目 地層の H 行目の情報

Output

入力データセットごとに、最少費用または NA を出力します。

Sample Input

3 3
100 10 10
-100 -20 -100
-100 -20 -100
-100 -20 -100
3 3
100 10 10
-100 -20 -100
-100 -20 -20
-100 -60 -20
3 3
100 10 3
-100 -20 -100
-20 -20 -20
-20 -100 -20
3 3
100 3 3
-100 -20 -30
-100 -20 2
-100 -20 -20
4 5
1500 5 4
-10 -380 -250 -250
-90 2 -80 8
-250 -130 -330 -120
-120 -40 -50 -20
-250 -10 -20 -150
0 0

Output for the Sample Input

60
80
NA
50
390

Source: PC Koshien 2010 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2010
http://www.pref.fukushima.jp/pc-concours/