책자 배포

정보올림피아드 일본위원회는 상하 관계가 아주 엄격한 조직이다. 위원장은 한 명이고, 위원장을 제외한 모든 사람은 상사가 정확히 한 명 있다. 그리고 위원회에 속한 사람마다 의욕이라는 수치가 정해져 있다.

지금 정보올림피아드 일본위원회에서 새로운 프로젝트를 시작하려 한다. 그 프로젝트가 성공할지 여부는 참가하는 사람 수와 무관하고, 참가하는 사람의 의욕 수치의 합으로 결정된다고 여겨진다.

위원장은 그 프로젝트에 관한 자세한 설명을 적은 책자를 m권 만들었다. 프로젝트에 참가하는 사람은 반드시 이 책자를 읽어야 하고, 책자를 읽은 사람은 반드시 프로젝트에 참가한다.

처음에는 위원장이 m권의 책자를 모두 가지고 있다. 위원장과 책자를 1권 이상 받은 사람은 먼저 책자를 읽고, 부하가 있으면 부하에게 책자를 넘긴다. 부하란 그 사람을 상사로 두는 사람을 말한다. 책자 1권은 부하 중 한 명에게 넘길 수 있다. 같은 부하에게 책자를 2권 이상 넘겨도 되고, 책자를 한 권도 받지 못하는 부하가 있어도 된다. 책자를 한 번 읽으면 책자를 손에 남겨 둘 필요는 없다.

각 사람의 상사와 의욕 수치, 그리고 만든 책자의 권수 m이 입력으로 주어질 때, 프로젝트에 참가하는 사람의 의욕 합계의 최댓값을 구하는 프로그램을 작성하시오.

입력의 첫째 줄에는 두 정수 n, m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 1000)이 공백으로 구분되어 쓰여 있다. 이는 정보올림피아드 일본위원회의 사람 수가 n명이고, 만든 책자의 권수가 m권임을 나타낸다.

다음 n줄에는 각 사람의 상사와 의욕 수치가 쓰여 있다. i + 1번째 줄 (1 ≤ i ≤ n)에는 두 정수 si, ai (0 ≤ si < i, 1 ≤ ai ≤ 10 000)가 공백으로 구분되어 쓰여 있다. 이는 사람 i의 상사가 사람 si이고, 사람 i의 의욕 수치가 ai임을 나타낸다. si가 0이면 사람 i가 위원장임을 나타낸다. (si < i이므로 어떤 사람의 상사는 반드시 그 사람의 번호보다 작은 번호를 가지며, 사람 1은 반드시 위원장이다.)

출력은 표준 출력으로 한다. 프로젝트에 참가하는 사람의 의욕 합계의 최댓값을 나타내는 정수 하나를 출력하시오.