Distribution(冊子の配布) - joi2009-day4

時間制限: 2秒

メモリ制限: 256MB

情報オリンピック日本委員会は上下関係がとても厳格な組織である. 委員長は一人で, 委員長以外の全ての人間はただ一人の上司を持つ. そして, 委員会に属する人間には, 一人一人やる気の数値なるものが定まっている.

今, 情報オリンピック日本委員会の中で, 新たなプロジェクトを立ち上げることとなった. そのプロジェクトが上手くいくかどうかは, 参加する人間の人数には関係なく, 参加する人間のやる気の数値の合計によると考えられている.

委員長はそのプロジェクトに関する詳細な説明を記述した冊子をm冊制作した. プロジェクトに参加する人間は, 必ずこの冊子を読まなければならず, 冊子を読んだ人間は必ずプロジェクトに参加する.

最初は委員長がm冊全ての冊子を持っている. 委員長及び冊子を1冊以上渡された人間は, まず冊子を読み, 部下が居れば冊子を部下に渡す. 部下とは, その人間を上司として持つ人間のことである. 1冊の冊子は部下のうちの一人に渡すことができる. 同じ部下に2冊以上の冊子を渡してもよく, 冊子が1冊も渡されない部下がいても良い. 1度冊子を読めば, 手元に冊子を残しておく必要はない.

入力としてそれぞれの人間の上司とやる気の数値, そして製作した冊子の冊数mが与えられた時, プロジェクトに参加する人間のやる気の合計の最大値を答えるプログラムを作成せよ.

Input.

入力ファイルdistribution.inの1行目には2つの整数n,m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 1000) が空白を区切りとして書かれている. これは情報オリンピック日本委員会の人数がn人であり, 製作した冊子の冊数がm冊であることを表す.

次のn行には, それぞれの人間の上司とやる気の数値が書かれている. i+1行目(1 ≤ i ≤ n) には2つの整数s[i], a[i] (0 ≤ s[i] < i, 1 ≤ a[i] ≤ 10 000) が空白を区切りとして書かれている. これは, 人間iの上司が人間s[i]であり, 人間iのやる気の数値がa[i]であることを表す. s[i]が0の時, 人間iは委員長であることを表す. (s[i] < i であることから, ある人間の上司は必ずその人間の番号より若い番号を持ち, 人間1は必ず委員長である.)

Output.

出力は, 標準出力に行うこと. プロジェクトに参加する人間のやる気の合計の最大値を表す1 つの整数を出力せよ.

採点基準

採点用データのうち, 配点の50% 分については, n ≤ 500, m ≤ 100 を満たす.

例

distribution.in	標準出力
`5 2 0 10 1 3 2 5 2 2 1 4`	`22`