LaNaic

„Fie ploaie sau furtună
O shaorma-i numa’ bună”

Toată Orăștia știe că Naic are cea mai tare shaormerie din oraș. La câte comenzi are, el nu mai concurează cu Siclam și GurgerBrill, ci cu KFC și McDonald’s. Pentru că problemele de la barajul de astăzi sunt prea ușoare, ai decis să treci pe la fratele tău Naic să îți iei o shaorma, dar bineînțeles că înaintea ta sunt 150 de comenzi de la pompieri și de la IGO. Pentru că el nu se uită urât la tine cât timp aștepți comanda, așa cum fac cei de la Siclam și GurgerBrill, te lasă să te joci pe OEIS 5 (Orăștie Entertainment Interactive System 5). Jocul favorit al lui Naic de pe stațiunea de joacă 5 este următorul:

Se dă un arbore cu $N$ noduri în care fiecare muchie poate avea valoarea $0$ sau $1$.

Un drum din arbore de la un nod la oricare alt nod se numește $K$-alternant dacă cel mult $K$ muchii consecutive au aceeași valoare.

Există posibilitatea de a efectua operații de tipul _„schimbă valoarea unei muchii din $0$ în $1$ sau din $1$ în $0$”.

Să se afle lungimea celui mai lung lanț $K$-alternant care se poate obține dacă se poate schimba valoarea a cel mult $M$ muchii.

Cerință

Scrie un program care să rezolve jocul de pe consolă dacă tot au fost așa de ușoare problemele din ziua asta.

Date de intrare

Pe prima linie se află $N , K$ și $M$. Pe următoarele $N − 1$ linii se găsesc trei întregi $x, y$ și $c$ cu semnificația că există muchie între nodul $x$ și nodul $y$ cu valoarea $c$.

Date de ieșire

Pe singura linie a fișierului de ieșire se va afișa lungimea maximă a unui lanț $K$-alternant.

Restricții și precizări

• $1 ≤ N ≤ 200 \ 000$
• $2 ≤ K < N$
• $0 ≤ M < N$

Exemplu

stdin

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

stdout

6

Explicație

Dacă schimbăm muchia $1-7$, obținem lanțul $9-8-7-1-2-3-4$, cu lungimea de $6$ muchii, pe care apar cel mult două valori egale consecutive. Vezi figura de mai jos.