題目 1318:
選課
時間限制: 2s
內(nèi)存限制: 192MB 提交: 223 解決: 51
題目描述
學(xué)校實行學(xué)分制。每門的必修課都有固定的學(xué)分，同時還必須獲得相應(yīng)的選修課程學(xué)分。學(xué)校開設(shè)了N（N< 300）門的選修課程，每個學(xué)生可選課程的數(shù)量M是給定的。學(xué)生選修了這M門課并考核通過就能獲得相應(yīng)的學(xué)分。
在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如《Frontpage》必須在選修了《Windows操作基礎(chǔ)》之后才能選修。我們稱《Windows操作基礎(chǔ)》是《Frontpage》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。每門課都有一個課號，依次為1，2，3，…。 例如: 
表中1是2的先修課，2是3、4的先修課。如果要選3，那么1和2都一定已被選修過。 你的任務(wù)是為自己確定一個選課方案，使得你能得到的學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時間上的沖突。
輸入格式
輸入文件的第一行包括兩個整數(shù)N、M（中間用一個空格隔開）其中1≤N≤300,1≤M≤N。
以下N行每行代表一門課。課號依次為1，2，…，N。每行有兩個數(shù)（用一個空格隔開），第一個數(shù)為這門課先修課的課號（若不存在先修課則該項為0），第二個數(shù)為這門課的學(xué)分。學(xué)分是不超過10的正整數(shù)。
輸出格式
輸出文件只有一個數(shù),實際所選課程的學(xué)分總數(shù)。
樣例輸入
7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2
樣例輸出
13