Олимписките игри оваа година ќе се одржат во Рио де Жанеиро, Бразил. Во Олимпиското село има N објекти во кои ќе се одржуваат настани на олимпијадата. Објектите се меѓусебно поврзани со точно N - 1 двонасочни патеки, распоредени така што меѓу секои два објекта постои пат (составен од една или повеќе надоврзани патеки).

Организаторите на олимпијадата сакаат да направат интересна церемонија на предавање на факелот. Според нивната идеја, во секој објект се поставува по точно еден познат спортист, а факелот треба да се предава како штафета од еден спортист на друг.

Штафетата треба да почне од некој (кој било) објект S и да заврши во друг (кој било) објект E (S е различно од E). Почнувајќи од објектот S, спортистот (кој е во Ѕ) го пренесува факелот преку точно една патека до соседен објект. Таму тој го предава факелот на спортистот кој стои таму и тој ја продолжува штафетата изминувајќи повторно една нова патека. Ова продолжува додека факелот да дојде до објектот E (притоа, се внимава еден спортист да го добие факелот НАЈМНОГУ еднаш, како и еден објект да не биде посетен повеќе пати).

Времетраење на носењето на факелот од страна на еден спортист е потребното време да се измине патеката по која тој се движи (времето на изминување на една иста патека е исто за сите спортисти). Просечното времетраење на носење на факелот од страна на спортистите се пресметува како МЕДИЈАНА од времетраењата на носењето на факелот на секој од спортистите кои го носат факелот.

Нека t[i], i = 0, …, k - 1 се времињата на носење на факелот од страна на k-те спортисти кои учествуваат во штафетата, подредени по големина - од најмало кон најголемо. Медијана од времињата е вредноста t[k/2], каде делењето со 2 е целобројно делење. На пример, ако t = {1, 5, 7}, тогаш t[3/2] = t[1] = 5, па медијаната е 5. Ако пак t = {2, 4, 7, 12}, тогаш t[4/2] = t[2] = 7, па медијаната е 7.

Одлучено е дека бројот на спортисти кои ќе го поносат факелот треба да е најмалку L, а најмногу H. Најди го максималното просечно времетраење на носењето на факелот, имајќи го предвид претходниот услов.

Влез

Во првиот ред се дадени 3 броја, одделени меѓу себе со по едно празно место: бројот на објекти - N, минималниот број на спортисти кои ќе го носат факелот - L, како и максималниот број на спортисти кои ќе го носат факелот - H (1 <= L <= H < N <= 100 000).
Во секој од следните N - 1 редови се наоѓаат по 3 броја: А, B и C, одделени меѓу себе со по едно празно место, кои означуваат дека меѓу објектот A и објектот B постои патека и дека времетраењето на изминување на патеката е C (1 <= A, B <= N, A <> B, 1 <= C <= 1 000 000 000).

Забелешка:
За тест случаи кои носат 25% од поените ќе важи: N <= 100.
За тест случаи кои носат 25% од поените ќе важи: 100 < N <= 1 000.

Излез

Во првиот и единствен ред е запишан еден број - бараното максималното просечно времетраење на носењето на факелот.

Ограничувања

Временско ограничување: 2 seconds
Мемориско ограничување: 64 megabytes

Примери

влез
6 3 4
1 2 1
2 3 1
3 4 1
4 5 2
5 6 2

излез
2

влез
5 1 4
1 2 1
1 3 4
3 4 7
3 5 2

излез
7

влез
8 3 6
1 2 9
2 3 7
3 4 7
4 5 8
5 8 2
3 6 3
2 7 4

излез
8

Објаснување за првиот тест пример: Во штафетата може да учествуваат 3 или 4 спортисти. Една рута на штафетата е: 2-3-4-5 (почетниот објект е 2, а крајниот 5, бројот на спортисти во штафетата е 3). Во овој случај просечното времетраење на носењето на факелот е 1 (медијана од времетраењата на носењето на факелот на секој од спортистите {1,1,2}). Друга рута на штафетата е: 2-3-4-5-6 (почетниот објект е 2, а крајниот 6, бројот на спортисти во штафетата е 4). Во овој случај просечното времетраење на носењето на факелот е 2 (медијана на {1,1,2,2}). Од сите можни рути на штафетата максималното просечно времетраење на носењето на факелот е 2.

Објаснување за вториот тест пример: Пример на рута со максимално просечно времетраење е рутата 1-3-4. Просечното времетраење е 7 (медијана на {4,7})