原題來自：CTSC 1997

大學(xué)實(shí)行學(xué)分制。每門課程都有一定的學(xué)分，學(xué)生只要選修了這門課并通過考核就能獲得相應(yīng)學(xué)分。學(xué)生最后的學(xué)分是他選修各門課的學(xué)分總和。

每個(gè)學(xué)生都要選擇規(guī)定數(shù)量的課程。有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識(shí)，必須在選了其他的一些課程基礎(chǔ)上才能選修。例如《數(shù)據(jù)結(jié)構(gòu)》必須在選修了《高級(jí)語言程序設(shè)計(jì)》后才能選修。我們稱《高級(jí)語言程序設(shè)計(jì)》是《數(shù)據(jù)結(jié)構(gòu)》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。為便于表述，每門課都有一個(gè)課號(hào)，課號(hào)依次為 1,2,3,?。

下面舉例說明：

上例中課號(hào) 1 是課號(hào) 2 的先修課，即如果要先修課號(hào) 2，則課號(hào) 1 必定已被選過。同樣，如果要選修課號(hào) 33 ，那么課號(hào) 1 和 課號(hào) 2 都一定被選修過。

學(xué)生不可能學(xué)完大學(xué)開設(shè)的所有課程，因此必須在入學(xué)時(shí)選定自己要學(xué)的課程。每個(gè)學(xué)生可選課程的總數(shù)是給定的。請(qǐng)找出一種選課方案使得你能得到的學(xué)分最多，并滿足先修課優(yōu)先的原則。假定課程間不存在時(shí)間上的沖突。

輸入的第一行包括兩個(gè)正整數(shù) M,N，分別表示待選課程數(shù)和可選課程數(shù)。

接下來 M 行每行描述一門課，課號(hào)依次為 1,2,?,M。每行兩個(gè)數(shù)，依次表示這門課先修課課號(hào)（若不存在，則該項(xiàng)值為 0）和該門課的學(xué)分。

各相鄰數(shù)值間以空格隔開。

數(shù)據(jù)范圍與提示：

1≤N≤M≤100，學(xué)分不超過 20。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃