I Hate Any Examinations!

ストーリー

かみゅ～君は非常に定期テストが嫌いです。
しかし、定期テストの得点が評価に大きく影響するのでそうも言っていられません。
そこで、適度にリフレッシュをしつつ勉強のモチベーションを上げ、よりよいパフォーマンスを出すことを目標にしました。

問題文

かみゅ～君には、モチベーション、現実逃避度、勉強量、依存耐性のステータスがあります。

はじめ、モチベーション、現実逃避度、勉強量はすべて $0$ です。また、依存耐性は常に $P$ です。

かみゅ～君は、定期テストまでに $H$ 時間行動することにしました。 行動可能な時間を $1$ 時間ずつに区切り、各時間には、必ず勉強かリフレッシュのいずれかを選び、その行動を $1$ 時間ぶっ続けで行います。

リフレッシュは $N$ 種類あり、$i$ 番目のリフレッシュには、モチベーション変化 $m_i$ と依存度 $a_i$ があります。

$1$ 時間の行動の後、かみゅ～君のステータスに以下の変化が起きます。

• リフレッシュ $i$ をしていた場合
  • モチベーション が $m_i$ だけ上昇する。
  • 現実逃避度 が $a_i$ だけ上昇する。
• 勉強をしていた場合
  • モチベーション が $D_M$ だけ減少する。
  • 現実逃避度 が $D_A$ だけ減少する。
  • 勉強量 が、上の $2$ つの変化を反映した後のモチベーションの値だけ上昇する。

ただし、モチベーション の値の上限は $100$ であり、計算結果が $100$ を超える場合は $100$ となります。

また、勉強によって モチベーション や 現実逃避度 の値が減少する場合、それぞれ $0$ 未満にはならず、計算結果が $0$ 未満になる場合は $0$ になります。

$H$ 時間の行動の中で、現実逃避度 が一度でも 依存耐性 $P$ より大きい値になると、かみゅ～君はリフレッシュに依存して勉強から逃げてしまうので、それ以降は勉強を選べなくなり、残りの時間は全ていずれかのリフレッシュを行います。

$H$ 時間の行動を終え、テスト本番時点での 勉強量 として取り得る最大値を求めてください。

制約

• $1\le N\le10$
• $1\le P\le10^2$
• $1\le H\le240$
• $0\le D_M\le10^2$
• $0\le D_A\le P$
• $0\le m_i\le10^2$
• $0\le a_i\le P$
• 入力は全て整数

入力

出力

テスト本番時点での勉強量の最大値を一行で出力してください。

入力例1

2 10 4
3 2
5 2
10 5

出力例1

31

例えば以下のように行動すると、勉強量 $31$ を得ることができます。

• 最初、かみゅ～君のモチベーション、現実逃避度、勉強量は全て $0$ です。
• $1$ 時間目、リフレッシュ $2$ を行う。モチベーションが $10$ 上昇して $10$ になり、現実逃避度が $5$ 上昇して $5$ になる。
• $2$ 時間目、リフレッシュ $2$ を行う。モチベーションが $10$ 上昇して $20$ になり、現実逃避度が $5$ 上昇して $10$ になる。
• $3$ 時間目、勉強を行う。モチベーションが $3$ 減少して $17$ になり、現実逃避 度が $2$ 減少して $8$ になる。そして、勉強量が $17$ 上昇して $17$ になる。
• $4$ 時間目、勉強を行う。モチベーションが $3$ 減少して $14$ になり、現実逃避 度が $2$ 減少して $6$ になる。そして、勉強量が $14$ 上昇して $31$ になる。

かみゅ～君が $4$ 時間どのように行動しても勉強量が $31$ を超えることはありません。よって、$31$ を出力してください。

入力例2

1 10 4
3 2
51 3

出力例2

191

モチベーションの上限は $100$ であることに注意してください。

入力例3

1 100 240
0 0
0 0

出力例3

0

残念ながらこの環境ではかみゅ～君のモチベーションは常に $0$ です。
よって、どのように行動しても勉強量は $0$ です。