2 - プレゼント (Presents) 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MiB

配点 : 100 点

問題文

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 \leqq i \leqq N) には整数 A_{i}, B_{i}, C_{i}, D_{i} が空白を区切りとして書かれており,番号 i の生徒は,番号 A_{i} (1 \leqq A_{i} \leqq N,A_{i} \ne i) の生徒に B_{i} 個のお菓子をプレゼントすること,自分が作ったお菓子と同じ種類のお菓子をもらったときに得る「嬉しさ」が C_{i} ポイント,違う種類のお菓子をもらったときに得る「嬉しさ」が D_{i} ポイントであることを表す.

出力

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

制約

すべての入力データは以下の条件を満たす.

  • 2 \leqq N \leqq 100\,000.
  • 1 \leqq B_{i} \leqq 1\,000\,000 (1 \leqq i \leqq N).
  • 1 \leqq C_{i} \leqq 1\,000\,000 (1 \leqq i \leqq N).
  • 1 \leqq D_{i} \leqq 1\,000\,000 (1 \leqq i \leqq N).

小課題

小課題 1 [10 点]

  • N \leqq 16 を満たす.

小課題 2 [20 点]

  • N \leqq 5\,000 を満たす.

小課題 3 [70 点]

追加の制限はない.

入出力例

入力例 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 となる.


出典

JOI 2012/2013 春季トレーニング合宿 Contest Day4