Kinugoshi's Break Fast

きぬごし君は、朝ごはんのビュッフェに来ています。
ビュッフェには 種類の料理があり、それぞれジャンルが 、おいしさが 、腹持ちが です。
きぬごし君は おなかが空いていて、食べた料理の腹持ちの合計が を超えない限り食べられますが、 食品ロスを避けるため取った料理をすべて食べてもおなかがいっぱいにならないようにします。 つまり、食べた料理の腹持ちの合計が 以下まで食べられます。
きぬごし君には料理のジャンルによって好き嫌いがあり、和食は ,洋食は ,中華は 好きです。
料理のおいしさ ジャンルの好きさ がきぬごし君の満足度になります。
きぬごし君は同じ料理をふたつ食べると飽きてしまうので、同じ料理は食べません。
食べた料理の満足度の合計としてありえる最大値を出力してください。

入力は全て整数

• 
  ・
  ・
  ・
• 
  において、和食は 、洋食は 、中華は に当てはまります。

食べた料理の満足度の合計としてありえる最大値を1行で出力し、改行してください。

6 9
1 2 3
3 1 2
2 1 1
3 2 3
1 1 2
3 1 1
1 85 5

94

3,5,6番目の食べ物を食べるのが最善です。

0 0
1 1 1

0

ビュッフェには1つも料理がなかったようです。