拜特兰王国（Kingdom of Byteland）几乎全被森林和河流覆盖。小河汇聚成大河，大河再次汇聚，最终所有的河流都流入一条大河。这条大河在拜特城（Bytetown）附近流入大海。
拜特兰有 $n$ 个伐木工村庄，每个村庄都坐落在河流旁。目前，拜特城有一座大型锯木厂，处理王国中砍伐的所有树木。树木从村庄沿着河流漂流到拜特城的锯木厂。拜特兰国王决定在村庄中新建 $k$ 个额外的锯木厂，以减少将树木运往下游的成本。建造锯木厂后，树木不需要一直漂流到拜特城，而可以在它们沿下游遇到的第一家锯木厂进行处理。显然，在建有锯木厂的村庄附近砍伐的树木不需要通过河流运输。需要注意的是，拜特兰的河流不会分叉。因此，对于每个村庄，从该村庄到拜特城只有一条唯一的向下游方向的路径。
国王的会计计算了每个村庄每年砍伐的树木数量。你必须决定在哪里建造锯木厂，以使每年的树木总运输成本最小。河流运输成本为每棵树每公里 $1$ 分钱。
编写一个程序：
- 从标准输入读取村庄数量、要建造的额外锯木厂数量、每个村庄附近砍伐的树木数量以及河流的描述；
- 计算建造额外锯木厂后河流运输的最小成本；
- 将结果写入标准输出。
输入格式
输入的第一行包含两个整数：$n$ —— 除拜特城以外的村庄数量（$2 \le n \le 100$），以及 $k$ —— 要建造的额外锯木厂数量（$1 \le k \le 50$ 且 $k \le n$）。村庄编号为 $1, 2, \dots, n$，而拜特城的编号为 $0$。
接下来的 $n$ 行，每行包含三个由单个空格分隔的整数。第 $i+1$ 行包含：
- $w_i$ —— 村庄 $i$ 每年砍伐的树木数量（$0 \le w_i \le 10000$），
- $v_i$ —— 从村庄 $i$ 出发向下游方向遇到的第一个村庄（或拜特城）（$0 \le v_i \le n$），
- $d_i$ —— 从村庄 $i$ 到 $v_i$ 的河流距离（以公里为单位）（$1 \le d_i \le 10000$）。
保证一年内将所有树木漂流到拜特城锯木厂的总成本不超过 $2\,000\,000\,000$ 分。
在 $50\%$ 的测试用例中，$n$ 不超过 $20$。
输出格式
输出的第一行也是唯一的一行应该包含一个整数：河流运输的最小成本（以分钱为单位）。
样例
输入样例 1
4 2 1 0 1 1 1 10 10 2 5 1 2 3
输出样例 1
4
说明
上图展示了样例输入的数据。圆圈内的数字表示村庄编号。圆圈下方的数字表示该村庄每年砍伐的树木数量。箭头旁边的数字表示河流的长度。
锯木厂应该建在村庄 2 和 3。