問題文

沙耶花は通っている高校の先輩に一方的な好意を寄せています.
しかし, 先輩は $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$ 円減ります.
  • 先週にデートの約束をしていない場合, 何も起きません.

入力

$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}$
• 入力はすべて整数

出力

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

サンプル

3
3 3 3
1 2 3
4 3 2

3

6
2 3 2
1 4 1
1 1 3
1 3 2
1 4 2
2 4 4

8

4
15 15 20
15 100 15
5 15 100
5 5 35

0