Problem Description

题目描述

在星际机甲研发中心，首席工程师需要为新一代机甲“星辰号”规划科技树的点亮方案。

科技树中共有 $N$ 个研发节点，每个节点研发完成后能提升机甲一定的“综合战力”，分别记作 $s_1, s_2, \cdots, s_N$。科技树的解锁存在严格的依赖关系：每个节点有且仅有一个“前置节点”（或者没有前置节点）。若节点 $a$ 是节点 $b$ 的前置节点，意味着必须先投入资源完成节点 $a$ 的研发，才能解锁并研发节点 $b$。

由于研发预算和时间的限制，工程师最多只能选择 $M$ 个节点进行研发。请问在满足前置依赖条件的前提下，如何选择 $M$ 个节点，能使机甲获得的“综合战力”最大？

题目保证科技树的依赖关系构成合法的森林结构（即不会出现循环依赖，如 $a$ 依赖 $b$ 且 $b$ 依赖 $a$ 的情况）。

输入格式

第一行有两个整数 $N$，$M$ 用空格隔开 $(1 \leq N \leq 300, 1 \leq M \leq 300)$，分别表示科技树的节点总数和最多能研发的节点数量。 接下来的 $N$ 行，第 $i+1$ 行包含两个整数 $k_i$ 和 $s_i$。$k_i$ 表示第 $i$ 个节点的前置节点编号，$s_i$ 表示第 $i$ 个节点能提供的战力值。若 $k_i=0$ 表示该节点为基础节点，无需前置即可直接研发 $(0 \leq k_i \leq N, 1 \leq s_i \leq 20)$。

数据保证至少存在一个 $k_i=0$，即至少有一个基础节点。

输出格式

只有一行，一个整数，表示选择 $M$ 个节点能获得的最大综合战力。

输入输出样例 #1

输入 #1

7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

输出 #1

13