Poisonous Full Course: Renewal

問題文

名無月くんは最近保健所の指導が入ったと聞く毒入りフルコースの店に行くことにしました。この店はリニューアルしており、またそれに伴ってレストランの横には病院が併設されました。

レストランで提供される料理には毒あるいは解毒剤が含まれています。それぞれ以下のような効果を発揮します：

• 毒 $k$（$1 \leq k \leq K$）入りの料理を食べると、名無月くんの状態は以下のように変化します：
  • 名無月くんが毒$k$を患っていない場合：毒$k$を患います。
  • 名無月くんが毒$k$を患っている場合：名無月くんはこの料理を食べ終えたあとに倒れ、併設の病院に緊急搬送されます。
    • このとき、毒$k$はこの料理を食べた時刻のうちに無料で治療されますが、他の毒は治療されません。
• 解毒剤 $k$（$1 \leq k \leq K$）入りの料理を食べると、名無月くんの状態は以下のように変化します：
  • 名無月くんが毒$k$を患っていない場合：何も起こりません。
  • 名無月くんが毒$k$を患っている場合：毒$k$を治療します。

時刻$i$（$1 \leq i \leq N$）では名無月くんは以下の行動のうち一つを取ることができます：

• レストランに居るとき、料理$i$を食べる。
  • その料理を食べたことにより幸福度$A_i$を獲得します。
  • $X_i \gt 0$ のとき、料理には毒$X_i$が入っています。
  • $X_i \lt 0$ のとき、料理には解毒剤$-X_i$が入っています。
• 病院に居るとき、解毒剤$k$を購入して服用する。コスト$C_k$がかかり、毒$k$を患っている場合は毒$k$が治療されます。
• 病院からレストランに戻る。このとき、毒をすべて治療している必要はありません。
• 何もしない。もし料理が出されていた場合は、その料理は廃棄されます。

緊急搬送以外の方法でレストランから病院に行く方法はないことに注意してください。また、名無月くんは料理を一瞬で食べ終えることができます。

名無月くんは時刻$0$の時点でレストランにおり、またどの種類の毒を患っていません。

食べた料理の幸福度から病院で支払ったコストを引いた値を満足度とします。満足度の最大値を求めてください。
なお、全ての行動が終わった時点で病院に居ても構いません。

制約

• 入力される値はすべて整数
• $1 \leq N \leq 1000$
• $1 \leq K \leq 8$
• $-K \leq X_i \leq K$、$X_i \ne 0$
• $-10^9 \leq A_i \leq 10^9$
• $1 \leq C_k \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

出力

満足度の最大値を出力してください。

サンプル 1

入力

4 1
5 8 6 9
1 -1 1 1
4

出力

28

例えば、以下のように行動することで満足度 $28$ を得られます。

• 時刻 $1$：料理 $1$ を食べ、毒 $1$ を患う。
• 時刻 $2$：料理 $2$ を食べ、毒 $1$ を治療する。
• 時刻 $3$：料理 $3$ を食べ、再び毒 $1$ を患う。
• 時刻 $4$：料理 $4$ を食べ、病院に緊急搬送される。

すべての料理を食べているため、これが最大です。

サンプル 2

入力

4 1
10 20 -100 40
1 1 -1 1
50

出力

70

例えば、以下のように行動することで満足度 $70$ を得られます。

• 時刻 $1$：料理 $1$ を食べ、毒 $1$ を患う。
• 時刻 $2$：料理 $2$ を食べ、病院に緊急搬送される。
• 時刻 $3$：病院からレストランに戻る。
• 時刻 $4$：料理 $4$ を食べる。

このとき、満足度は $10+20+40=70$ となり、これが最大です。

サンプル 3

入力

7 2
10 10 10 0 0 100 100
1 2 1 -1 -1 2 2
8 5

出力

225

例えば、以下のように行動することで満足度 $225$ を得られます。

• 時刻 $1$：料理 $1$ を食べ、毒 $1$ を患う。
• 時刻 $2$：料理 $2$ を食べ、毒 $2$ を患う。
• 時刻 $3$：料理 $3$ を食べ、病院に緊急搬送される。このとき、毒 $1$ のみが治療される。
• 時刻 $4$：病院で解毒剤 $2$ を購入して服用し、毒 $2$ を治療する。
• 時刻 $5$：病院からレストランに戻る。
• 時刻 $6$：料理 $6$ を食べ、毒 $2$ を患う。
• 時刻 $7$：料理 $7$ を食べ、病院に緊急搬送される。

このとき、満足度は $10+10+10-5+100+100=225$ となり、これが最大です。

サンプル 4

入力

5 1
100 -300 80 70 60
1 -1 1 1 1
12

出力

240

例えば、時刻 $1,3,5$ に料理を食べ、それ以外の時刻には何もしないことで、満足度 $100+80+60=240$ を得られます。

サンプル 5

入力

5 1
-100 -100 -100 -100 -100
1 -1 1 -1 1
10

出力

0

全ての料理を食べないことが最適です。