Adrian the Wonder Child 不久前开始为他的新项目编写代码。每天他都会在 Git 仓库中推送恰好一个提交，现在这个仓库看起来像一棵有 $n$ 个顶点的树。

众所周知，Adi 有好日子也有坏日子（通常是一个好日子后面跟着十个坏日子，但这对于本题来说不太重要）。因此，对于树中除根节点（初始提交）外的每个节点，他都将指向其父节点的边标记为 $0$ 或 $1$，具体取决于他是在坏日子还是好日子推送了相应的提交。

如果树中两个节点之间的路径中，连续相同值的边不超过 $k$ 条，则称该路径为 $k$-交替路径。

回顾他在某一天所做的工作，Adi 可以改变主意，认为那天是好日子还是坏日子；因此，他可以翻转相应节点与其父节点之间边的标签。

给定整数 $m$ 和 $k$，Adi 想知道通过翻转最多 $m$ 条边的标签，树中能获得的最长 $k$-交替路径的长度是多少。

输入格式

第一行包含三个整数：$n, k$ 和 $m$ ($3 \le n \le 2 \cdot 10^5, 2 \le k < n$ 且 $0 \le m < n$)。

接下来的 $n-1$ 行，每行包含三个整数：$x, y$ 和 $c$ ($1 \le x, y \le n$ 且 $c \in \{0, 1\}$)，表示节点 $x$ 和 $y$ 之间有一条标签为 $c$ 的边。

保证给定的边构成一棵树。

输出格式

输出一个整数，表示通过翻转最多 $m$ 条边的标签所能获得的最长 $k$-交替路径的长度。

样例

输入 1

9 3 2
1 2 0
2 3 1
3 4 1
4 5 1
1 6 1
1 7 0
7 8 0
8 9 1

输出 1

7