17753번 - Presents 서브태스크다국어

JOI 学園では毎年，ホワイトデーの時期に合わせて，お菓子のプレゼント交換会が行われる．今年のプ レゼント交換会には，1 から N までの学生番号が付いた N 人の生徒が参加する．それぞれの生徒は自分以 外の誰か 1 人の生徒のためにクッキーまたはケーキのいずれかを作る．番号 i の生徒は番号 A_i の生徒に， 作ったお菓子を B_i 個プレゼントする．

生徒によっては，自分が作ったものと同じ種類のお菓子をプレゼントされて味の研究をしたいという人 もいれば，自分が作ったものと違う種類のお菓子 (クッキーを作ったならケーキ，ケーキを作ったならクッ キー) をプレゼントされて楽しみたいという人もいる．番号 i の生徒は，自分が作ったものと同じ種類のお 菓子を 1 個もらうごとに「嬉しさ」が C_i ポイント加算され，自分が作ったものと違う種類のお菓子を 1 個 もらうごとに「嬉しさ」が D_i ポイント加算される．N 人の生徒がクッキーまたはケーキのいずれを作るか を上手く選んだとき，N 人の生徒の「嬉しさ」の合計は最大でいくつになりうるだろうか．

生徒がお菓子をプレゼントする相手と個数および「嬉しさ」の情報が与えられたとき，「嬉しさ」の合計 の最大値を求めるプログラムを作成せよ．

標準入力から以下の入力を読み込め．

• 1 行目には整数 N が書かれており，JOI 学園の生徒の人数を表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には整数 A_i, B_i, C_i, D_i が空白を区切りとして書かれており，番号 i の生徒は，番号 A_i (1 ≤ A_i ≤ N, A_i ≠ i) の生徒に B_i 個のお菓子をプレゼントすること，自分が作っ たお菓子と同じ種類のお菓子をもらったときに得る「嬉しさ」が C_i ポイント，違う種類のお菓子を もらったときに得る「嬉しさ」が D_i ポイントであることを表す．

標準出力に，N 人の生徒の「嬉しさ」の合計の最大値を 1 行で出力せよ．

• 2 ≤ N ≤ 100 000．
• 1 ≤ B_i ≤ 1 000 000 (1 ≤ i ≤ N)．
• 1 ≤ C_i ≤ 1 000 000 (1 ≤ i ≤ N)．
• 1 ≤ D_i ≤ 1 000 000 (1 ≤ i ≤ N)．