시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3 3 3 100.000%

문제

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

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

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

입력

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

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

출력

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

제한

  • 2 ≤ N ≤ 100 000.
  • 1 ≤ Bi ≤ 1 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Ci ≤ 1 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Di ≤ 1 000 000 (1 ≤ i ≤ N).

예제 입력 1

7
3 3 6 5
7 2 8 8
4 5 3 9
1 8 7 2
1 8 8 4
3 7 4 5
2 5 1 2

예제 출력 1

257

この例では,たとえば,番号 1, 2, 5, 6 の生徒がクッキー,番号 3, 4, 7 の生徒がケーキを作ることで,

  • 番号 1 の生徒はクッキー 8 個とケーキ 8 個をもらうので,「嬉しさ」は 88,
  • 番号 2 の生徒はケーキ 5 個をもらうので,「嬉しさ」は 40,
  • 番号 3 の生徒はクッキー 10 個をもらうので,「嬉しさ」は 90,
  • 番号 4 の生徒はケーキ 5 個をもらうので,「嬉しさ」は 35,
  • 番号 5 の生徒はお菓子をもらえないので,「嬉しさ」は 0,番号 6 の生徒はお菓子をもらえないので,「嬉しさ」は 0,
  • 番号 7 の生徒はクッキー 2 個をもらうので,「嬉しさ」は 4,

となり,「嬉しさ」の合計が 257 となる.