Lewis loves boxing, so he started a boxing club, hoping to raise funds for his training by hosting exhibition matches and selling tickets. Unfortunately, Lewis is not very popular, so the club only has two members—Lewis and his good friend Valtteri. The audience quickly grew tired of watching the same two people every night, ticket sales plummeted, and the boxing club was on the verge of bankruptcy. Desperate for a change, Lewis decided to save his club by hiring guest fighters.

Through a generous check, Lewis quickly hired two boxing stars—Max and Checo—who would join Lewis's club as guest performers. Over the next season, Lewis will schedule $n$ $(1 \le n \le 2 \times 10^5)$ matches. For each match, 2 people will be selected from the 4 current members. For the $i$-th $(1 \le i \le n)$ match, if it is Lewis vs. Valtteri, the ticket revenue is $a_i$. If it is one of them against a star, the revenue is $b_i$. If it is the two stars, Max vs. Checo, the revenue is $c_i$. The audience prefers high-level matches between stars rather than the amateurish brawls between Lewis and Valtteri, so $1 \le a_i < b_i < c_i \le 10^9$. Additionally, there are the following requirements:

1. Because the stars are very busy, they only agree to stay at Lewis's club for at most $t_m$ and $t_c$ matches, respectively. Let $p_m$ and $q_m$ be the first and last matches Max attends, and $p_c$ and $q_c$ be the first and last matches Checo attends. Then we must satisfy $q_m - p_m + 1 \le t_m$ and $q_c - p_c + 1 \le t_c$.
2. Lewis knows he is no match for the two stars and does not want to be beaten black and blue or knocked out. Therefore, he will not schedule himself to fight either of the two stars (which implies that the job of being beaten is secretly assigned by Lewis to his poor tool, Valtteri; let us mourn for the unfortunate Valtteri).

Lewis wants to maximize his total revenue. However, he is not very smart, so he considers a plan to be "revenue-maximizing" if it satisfies the following condition:

Definition ("Lewis's Optimal Plan"): A plan can be viewed as a sequence of length $2n$, where the $(2i-1)$-th and $2i$-th terms represent the participants of the $i$-th match. A plan is called "Lewis's Optimal Plan" if modifying any 1 position in the sequence cannot result in a valid plan with a strictly higher total revenue.

You, being clever, quickly realize that "Lewis's Optimal Plan" does not necessarily maximize total revenue and may not be unique. It is known that Lewis will choose one plan uniformly at random from all "Lewis's Optimal Plans" (two plans are identical if and only if the matchups for every day are the same; note that Max vs. Valtteri and Checo vs. Valtteri are considered different plans even though they generate the same revenue). What is the median of the ticket revenues among all plans that Lewis might eventually choose? (Output the answer with one decimal place.)

The input is read from standard input.

Line 1: Three positive integers $n, t_m, t_c$, as defined in the problem.

Next $n$ lines: Each line contains three positive integers $a_i, b_i, c_i$, representing the ticket prices for the three scenarios.

Output to standard output.

A single positive integer representing the median of the ticket revenues among all plans Lewis might eventually choose.

Examples

Input 1

2 1 1
1 10 100
1 2 3

Output 1

12.0

Note

There are 4 "Lewis's Optimal Plans":

1. Max vs. Checo, Lewis vs. Valtteri, revenue $100 + 1 = 101$
2. Valtteri vs. Max, Valtteri vs. Checo, revenue $10 + 2 = 12$
3. Valtteri vs. Checo, Valtteri vs. Max, revenue $10 + 2 = 12$
4. Lewis vs. Valtteri, Max vs. Checo, revenue $1 + 3 = 4$

The median is $(12 + 12) / 2 = 12$.

Input 2

3 1 3
1 2 3
5 6 12
1 5 6

Output 2

14.0