점핑 사다리

여러 층으로 된 직사각형 건물이 있다. 각 층에는 막대기 하나가 놓여 있으며, 막대기의 길이는 층마다 다를 수 있다. 시간 0부터 모든 막대기는 동시에 일정한 속도로 움직인다. 각 막대기는 왼쪽에서 오른쪽으로 움직이거나 오른쪽에서 왼쪽으로 움직이며, 속도는 양의 정수이다.

시간 0에 각 막대기는 건물의 왼쪽 벽 또는 오른쪽 벽에 닿아 있다. 이후 막대기는 주어진 방향과 속도로 움직이다가, 막대기의 한쪽 끝이 왼쪽 벽 또는 오른쪽 벽에 닿으면 즉시 방향을 바꾸어 계속 움직인다.

그림 1. 시간 0의 초기 상태

철수는 처음에 가장 아래층의 막대기 위에 있다. 철수는 다음 두 조건에 따라 움직일 수 있다.

조건 1) 현재 서 있는 막대기 위에서는 시간이 걸리지 않고 원하는 위치로 이동할 수 있다.

조건 2) 정수 $K$가 주어진다. 철수가 현재 있는 층에서 위로 최대 $K$개 층 안에 있는 어떤 막대기의 구간이, 현재 막대기 위의 어떤 위치와 겹치면 철수는 시간이 걸리지 않고 그 위층 막대기로 수직 이동할 수 있다. 구간의 양 끝점에서 만나는 경우도 겹친 것으로 본다.

예를 들어 $K=3$일 때, 그림 1의 초기 상태에서 철수는 네 번째 층의 막대기로 바로 올라갈 수 있고, 이어서 가장 위층의 막대기로 바로 올라갈 수 있다. 따라서 이 경우 가장 위층에 도달하는 데 걸리는 시간은 0이다.

시간 0의 초기 상태에서 출발해, 철수가 가장 아래층 막대기에서 가장 위층 막대기로 올라가는 데 필요한 최소 시간을 구하시오.

첫째 줄에 층 수 $N$, 층의 길이 $L$, 정수 $K$가 주어진다. 아래층은 1층이고 가장 위층은 $N$층이다.

다음 $N$개 줄 중 $i$번째 줄에는 $i$층 막대기의 길이 $l_i$, 초기 이동 방향 $d_i$, 이동 속도 $v_i$가 주어진다. $d_i=0$이면 막대기가 처음에 왼쪽 벽에 닿아 있으며 오른쪽으로 움직인다는 뜻이고, $d_i=1$이면 처음에 오른쪽 벽에 닿아 있으며 왼쪽으로 움직인다는 뜻이다.

입력은 다음 조건을 만족한다.

• $1 \le N \le 1000$
• $1 \le L \le 3000$
• $1 \le K \le N-1$
• $1 \le l_i \le L$
• $d_i$는 0 또는 1이다.
• $1 \le v_i \le L$

첫째 줄에 철수가 가장 아래층 막대기에서 가장 위층 막대기로 올라가는 데 필요한 최소 시간을 출력한다. 절대 오차 또는 상대 오차가 $10^{-5}$ 이하이면 정답으로 인정된다.