24136번 - 冊子の配布 (Distribution) 다국어

문제

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

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

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

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

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

입력

入力の 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 は必ず委員長である.)

출력

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

제한

힌트