花火大会は祭において最も刺激的なイベントの一つである. 花火大会において重要なことは,スイッチに導火線で繋がれている全ての爆薬が予定された時間に同時に爆発することである. 花火に使われる爆薬はとても危険なので, それらはスイッチから離れた場所に設置されている．また, 爆薬とスイッチは何本かの導火線により繋がれている. 複数の爆薬をスイッチに繋ぐため, 導火線は, [図 1] のような木構造における辺のように繋がれている. スイッチから着火すると，火花が導火線を伝わっていく. 火花が分岐点に到達すると, その分岐点に繋がれている全ての導火線に伝わる. 火花の伝わる速さは一定である. [図 1] は, 6 個の爆薬 {E1, E2, ..., E6} の繋がり方と, 各導火線の長さを表す. この図は, スイッチにおける着火時刻を としたときの爆発時刻も表す.
[図 1] 接続の設計図 (Connection Layout)
花火大会に参加しているヒョンミン (Hyunmin) は, 接続の設計図を作った. しかし残念ながら, 彼の作った設計図は, 爆薬が同時に爆発するとは限らないものだった. 何本かの導火線の長さを変更することで, 全ての爆薬が同時に爆発するようにしたい. 例えば, [図 1] の全ての爆薬が時刻 13 で爆発するためには, [図 2] の左側の図のように導火線の長さを調節すればよい. また, 同様に, [図 1] の全ての爆薬が時刻 14 で爆発するためには, [図 2] の右側の図のように導火線の長さを調節すればよい.
[図 2] 同時に爆発するための, 導火線の長さの変更方法の例
導火線の長さを変更するのにかかるコストは, 導火線の長さの差の絶対値に等しい. 例えば, [図 1] の設計図を [図 2] の左側の図のように変更した場合, コストの総和は 6 である. もし, [図 1] の設計図を [図 2] の右側の図のように変更した場合, コストの総和は 5 である.
分岐点同士の繋がり方を保持したまま, 導火線の長さを 0 にまで減らすこともできる.
接続の設計図が与えられたとき, 全ての爆薬が同時に爆発するように最小のコストで導火線の長さを調節するプログラム作成せよ.
入力 (Input)
入力される値は全て正整数である. N は分岐点の個数である. M は爆薬の個数である. 分岐点には 1 から N までの番号が付けられている. 番号 1 の分岐点にはスイッチが設置されている. 爆薬には N + 1 から N + M の番号が付けられている.
入力は以下の形式で与えられる:
N M P2 C2 P3 C3 : PN CN PN+1 CN+1 : PN+M CN+M
Pi (1 ≤ Pi < i) は, 番号 i の分岐点または爆薬に繋がれている分岐点を表す. Ci は，それらを繋ぐ導火線の長さを表す (1 ≤ Ci ≤ 109 ). スイッチ以外の各分岐点には，1 本以上の導火線が繋がれている. また，各爆薬には，ちょうど 1 本の導火線が繋がれている.
出力 (Output)
全ての爆薬が同時に爆発するように導火線の長さを変更するのにかかるコストの最小値を出力せよ.
例 (Example)
入力 (Input)
4 6 1 5 2 5 2 8 3 3 3 2 3 3 2 9 4 4 4 3
出力 (Output)
5
採点方法 (Scoring)
小課題 1 (7 点)
N = 1 を満たし, かつ, 1 ≤ M ≤ 100 を満たす.
小課題 2 (19 点)
1 ≤ N + M ≤ 300 を満たし, かつ, 着火するスイッチから爆薬までの距離の最大値は 300 以下である.
小課題 3 (29 点)
1 ≤ N + M ≤ 5,000 を満たす.
小課題 4 (42 点)
1 ≤ N + M ≤ 300,000 を満たす.