Country X has been devastated by an earthquake, leaving its national transportation network nearly paralyzed. The plan to rebuild the homeland is urgent. Country X consists of $N$ cities. The reconstruction team proposes that building only $N-1$ roads is sufficient to make any two cities reachable from each other. Consequently, the team quickly proposed a plan containing $N-1$ roads that satisfies the condition that all cities are pairwise reachable, and they calculated and evaluated the value $v(e)$ brought by the construction of each road $e$.

Because the reconstruction plan is complex and difficult, there are also certain budget limitations. Therefore, the government requires that the number of roads built in the first phase of the reconstruction project be $k$, satisfying $L \le k \le U$, meaning no fewer than $L$ roads and no more than $U$ roads. At the same time, to maximize utilization, it is required that these constructed roads form a simple path. That is, the $k$ constructed roads can form a sequence $e_1 = (p_1, q_1), e_2 = (p_2, q_2), \dots, e_k = (p_k, q_k)$, where for $1 \le i < k$, $q_i = p_{i+1}$.

The reconstruction team intends to modify their original plan to meet these requirements, which means finding a path $S$ within the original $N-1$ roads as the new plan, such that the average value of the roads in the new plan:

$$AvgValue = \frac{\sum_{e \in S} v(e)}{|S|}$$

is maximized. Here, $v(e)$ represents the value of road $e$, and $|S|$ represents the number of roads in the new plan. Please help the reconstruction team find an optimal plan.

Note: In this problem, the settings of $L$ and $U$ guarantee that a solution exists.

Input

The first line contains a positive integer $N$, representing the number of cities in Country X.

The second line contains two positive integers $L$ and $U$, representing the lower and upper bounds on the number of roads to be built in the first phase of the reconstruction plan as required by the government.

The next $N-1$ lines describe the original plan of the reconstruction team. Each line contains three positive integers $a_i, b_i, v_i$, representing the road $(a_i, b_i)$ with value $v_i$. Cities are labeled $1 \dots N$.

Output

Output a single line containing a real number $AvgValue$, which is the maximum average value. The result should be rounded to three decimal places.

Examples

Input 1

4
2 3
1 2 1
1 3 2
1 4 3

Output 1

2.500

Note 1

The original plan is shown in the figure below. In the new plan, choosing the path $(3, 1), (1, 4)$ yields an average value of $2.5$, which is the maximum average value.

Constraints

For 20% of the data, $N \le 5\,000$;

For another 30% of the data, $N \le 100\,000$, and the original plan is exactly a path (chain);

For 100% of the data, $N \le 100\,000$, $1 \le L \le U \le N-1$, $v_i \le 10^6$.