問題一覧 > 通常問題

No.974 最後の日までに

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : 沙耶花 / テスター : shibh308
8 ProblemId : 3724 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-05-07 20:08:30

問題文

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

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

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

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

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

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

入力

W
a1 b1 c1
:
aW bW cW

  • 1≤W≤52
  • 1≤ai,bi,ci≤1012
  • 入力はすべて整数

出力

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

サンプル

サンプル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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。