1181 - horilka & absinthe

Aphorismus

問題

rihoさんは高校生です。
定期考査に向けて勉強をしようと思いました。
ですが、長時間集中して勉強することができません。
そこで2種類の薬品を使ってこれを解決しようと考えました。
さて、定期考査まであとN日間勉強できます。
i日目には次の3種類のうち、一つを選んで行動できます。

1. そのまま勉強する。n_iの進捗を獲得する。
2. horilkaを摂取してから勉強する。h_iの進捗を獲得する。ただし、i+1日目は行動できない。
   horilkaを1つ消費する。horilkaを持っていないときは選べない。
3. absintheを摂取してから勉強する。a_i+a_i+1+a_i+2の進捗を獲得する。ただし、i+1日目, i+2日目は行動できない。
   このとき、absintheを3つ消費する。足りない場合はrihoさんは消滅する。

rihoさんはhorilkaをH個、absintheをA個もっています。
rihoさんが最適に行動した場合に得られる進捗の最大値を出力してください。
ただし、どのように行動してもrihoさんが消滅してしまう場合は-1を出力してください。また、定期考査の日(N+1日目)に行動ができなくなるような行動をとってはいけません。

入力

N
H A
n1 h1 a1
......
nN hN aN

出力

max

制約

• 1 ≤ $N$ ≤ 1000
• 0 ≤ $H$ ≤ 100
• 0 ≤ $A$ ≤ 100
• 0 ≤ $n_i$ ≤ 1000000
• 0 ≤ $h_i$ ≤ 1000000
• 0 ≤ $a_i$ ≤ 1000000

テストケース

例1

入力

5
0 0
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5

出力

15

例2

入力

3
3 3
1 2 3
3 5 6
2 9 0

出力

9