No.974 最後の日までに

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 36
作問者 : 沙耶花沙耶花 / テスター : shibh308shibh308
6 ProblemId : 3724 / 出題時の順位表
問題文最終更新日: 2020-01-18 00:26:31

問題文

沙耶花は通っている高校の先輩に一方的な好意を寄せています.
しかし, 先輩は $W$ 週間後に卒業してしまいます.
そこで, 彼女は卒業式当日に告白することに決めました.

はじめ, 先輩の沙耶花に対する好意をポイントとして数値化したもの(以下好感度)は0ポイントで, 沙耶花の所持金は0円です.
彼女は今週を1週目として, 1週目,2週目,...,$W$ 週目に,告白に向けた準備をすることにしました.

沙耶花は各 $i$ ( $1 \le i \le W$ )に対し, $i$ 週目には必ず以下の行動のうちどれか一つを取ります.

  • 学校に行く
    • 先週にデートの約束をしている場合, 好感度が$10^{100}$ポイント減ります.
    • 先週にデートの約束をしていない場合, 先輩に会い, 翌週にデートをすると約束します. ただし, $i=W$ のときは何も起きません.
  • アルバイトをする
    • 先週にデートの約束をしている場合, 好感度が$10^{100}$ポイント減り, 所持金が $a_i$ 円増えます.
    • 先週にデートの約束をしていない場合, 所持金が $a_i$ 円増えます.
  • デートをする
    • 先週にデートの約束をしている場合, 好感度が $b_i$ ポイント増え, 所持金が $c_i$ 円減ります.
    • 先週にデートの約束をしていない場合, 何も起きません.
なお,1週目の先週に,沙耶花は先輩とデートの約束をしていません.

また, 好感度や所持金の値は負になりえます.
特に, 所持金が負のとき, 彼女は借金を背負っています.
借金が利息によって勝手に増えたり, 借金があるためにデートに行けなかったりというようなことはありませんが,
$W$ 週目が終わった時点で借金を背負っている場合, 沙耶花は先輩の卒業式を迎えるより前に高校を辞めさせられます. (この場合, 沙耶花は先輩に告白できません.)

沙耶花が先輩に告白する時点における, 好感度の最大値を求めてください.

入力

$W$
$a_1\ b_1\ c_1$
$:$
$a_W\ b_W\ c_W$

  • $1\le W \le 52$
  • $1\le a_i,b_i,c_i \le 10^{12}$
  • 入力はすべて整数

出力

答えを出力してください.
最後に改行してください.

サンプル

サンプル1
入力
3
3 3 3
1 2 3
4 3 2
出力
3

1週目にアルバイトをし,2週目に学校に行き,3週目にデートをすることで達成できます.

サンプル2
入力
6
2 3 2
1 4 1
1 1 3
1 3 2
1 4 2
2 4 4
出力
8

サンプル3
入力
4
15 15 20
15 100 15
5 15 100
5 5 35
出力
0

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。