Umamusume Ranker

問題文

あなたはウマ娘の育成を行うことにしました。あなたが育成するウマ娘の初期基礎能力は $X$ 、初期スキルポイントは $Y$、体力最大値および初期体力は $Z$ です。

育成は全部で $N$ ターンからなり、 $i$ ターン目には以下の $3$ つのうちどれか $1$ つを選択します。

• トレーニングを行わせる。ウマ娘の基礎能力が $P_i$ 増加し、体力が $A_i$ 減少する。体力が $A_i$ 未満の場合、この選択は行えない。
• レースに出走させる。ウマ娘のスキルポイントが $S_i$ 増加し、体力が $B_i$ 減少する。体力が $B_i$ 未満の場合、この選択は行えない。
• 休憩させる。 ウマ娘の体力が $C_i$ 増加する。ただし、増加後の体力が体力最大値を上回ることは無い(上回る分は増加しない)。

育成の終了後、ウマ娘はそれぞれ $1$ から $M$ の番号が付けられた $M$ 個のスキルを習得出来ます。$i$ 番目のスキルの価値は $V_i$ であり、習得するには $W_i$ のスキルポイントを消費します。 スキルはスキルポイントが足りる限り何個でも習得できますが、同じ番号のスキルを $2$ 回以上習得することは出来ません。

育成およびスキルの習得を終えたウマ娘の評価点は、最終基礎能力を $X'$ 、習得したスキルの番号の集合を $T$ として以下の式で計算されます。

• $X'+\sum_{i∈T}^{}V_i$

育成によって達成出来るウマ娘の評価点の最大値を求めてください。

制約

• $1\leq X \leq 564$
• $1\leq Y \leq 120$
• $1\leq Z \leq 100$
• $1\leq N \leq 50$
• $1\leq P_i \leq 500$
• $1\leq S_i \leq 50$
• $1\leq A_i,B_i,C_i \leq Z$
• $1\leq M \leq 100$
• $1\leq V_i \leq 10000$
• $1\leq W_i \leq 1000$
• 入力は全て整数 　　

入力

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

出力

答えを出力してください。

入力例1

7 6 10
3
500 30 40
3 4 7
30 20 40
3 4 7
7 7 7
4
100 200 300 400
10 30 50 60

出力例1

807

$1$ ターン目にトレーニング、 $2$ ターン目に休憩、 $3$ ターン目にレースを選び、 $1$ 番目と $2$ 番目のスキルを習得するのが最適です。
最終基礎能力は $7+500=507$ 、習得したスキルが $1$ 番目と $2$ 番目なので、評価点は $507+(100+200)=807$ となります。
このケースでは全てのターンでレースを選択する、などは体力が足りないため不可能であることに注意してください。