Jumping Ladder

There is a rectangular building with several floors. Each floor has one rod, and rod lengths may differ from floor to floor. Starting at time 0, all rods move simultaneously at constant speeds. Each rod moves either from left to right or from right to left, and each speed is a positive integer.

At time 0, every rod touches either the left wall or the right wall of the building. As time passes, a rod moves in its given direction at its given speed. Whenever one endpoint of the rod touches the left wall or the right wall, the rod immediately reverses direction and continues moving.

Figure 1. The initial state at time 0

Chulsoo initially stands on the rod on the lowest floor. He can move according to the following two rules.

Rule 1) While standing on his current rod, he can move to any position on that rod without spending time.

Rule 2) An integer $K$ is given. If a rod on a floor at most $K$ floors above Chulsoo's current floor overlaps some position on his current rod, Chulsoo can move vertically to that upper rod without spending time. Touching at an endpoint counts as overlapping.

For example, when $K=3$, in the initial state shown in Figure 1, Chulsoo can move immediately to the rod on the fourth floor, and then immediately to the rod on the top floor. In that case, the time needed to reach the top floor is 0.

Starting from the initial state at time 0, find the minimum time Chulsoo needs to move from the rod on the lowest floor to the rod on the top floor.

The first line contains the number of floors $N$, the length of each floor $L$, and the integer $K$. The lowest floor is floor 1, and the top floor is floor $N$.

Each of the next $N$ lines describes one floor. The $i$-th of these lines contains the length $l_i$ of the rod on floor $i$, its initial moving direction $d_i$, and its speed $v_i$. If $d_i=0$, the rod initially touches the left wall and moves to the right. If $d_i=1$, the rod initially touches the right wall and moves to the left.

The input satisfies the following constraints.

• $1 \le N \le 1000$
• $1 \le L \le 3000$
• $1 \le K \le N-1$
• $1 \le l_i \le L$
• $d_i$ is either 0 or 1.
• $1 \le v_i \le L$

Print the minimum time Chulsoo needs to move from the rod on the lowest floor to the rod on the top floor. An absolute or relative error of at most $10^{-5}$ is accepted.