연세 포뮬러 1

시간 제한2초메모리 제한1024 MB

요약

원형 트랙을 M바퀴 도는 데 걸리는 최소 시간을 구합니다. 타이어는 순서대로만 바꿀 수 있고, 각 타이어의 성능은 시간이 지나며 떨어집니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

연세대학교 레이싱 팀이 대회에 참가했다. 대회를 완주하려면 트랙을 $M$ 바퀴 돌아야 한다. 트랙은 둘레의 길이가 $L$ 인 원이고, 시작 지점이 하나 있다. 시작 지점에서 출발해 $L$ 만큼 주행하면 한 바퀴를 돈 것으로 인정한다. 트랙이 원형이므로 시작 지점에서 $L$ 만큼 주행하면 다시 시작 지점에 도착한다.

레이싱카가 움직이려면 반드시 시작 지점에서 타이어를 장착한 뒤 주행해야 한다. 팀은 타이어 $N$ 개를 준비했고, 타이어는 순서대로만 교체할 수 있다. $i$ 번째 타이어로 교체한 직후 $i+1$ 번째 타이어로 바로 교체하는 것도 가능하다. $N$ 번째 타이어로 교체한 뒤에는 교체할 타이어가 없으므로 더 이상 교체할 수 없다.

타이어에는 매 분마다 성능이 있다. $t$ 분에 어떤 타이어의 성능이 $v$ 라면, $t+1$ 분까지 현재 위치에서 최대 $v$ 만큼 주행할 수 있다. 즉 $t$ 분에 레이싱카가 $x$ 에 있으면 $t+1$ 분에는 $[x,x+v]$ 안의 위치에 있을 수 있다. 어떤 위치에 도착하든 도착 시각은 $t+1$ 분이다. 따라서 주행 완료와 타이어 교체는 정수 시간에만 이루어진다.

타이어마다 옵션 $a_i$ , $b_i$ , $d_i$ 가 주어진다. $i$ 번째 타이어는 교체하는 순간 성능이 $a_i$ 가 된다. 이후 성능이 $b_i$ 에 이를 때까지 매 분 성능이 $d_i$ 씩 줄어든다. 즉 $t$ 분의 성능이 $v$ 일 때, $v=b_i$ 이면 $t+1$ 분의 성능도 $b_i$ 이고, $v>b_i$ 이면 $t+1$ 분의 성능은 $v-d_i$ 이다.

타이어는 시작 지점에서만 교체할 수 있다. 메카닉이 매우 숙련되어 있어서 타이어를 장착하거나 탈착하는 시간은 무시한다.

0분에 경기가 시작된다. 처음에는 레이싱카에 타이어가 장착되어 있지 않다. 연세대학교 레이싱 팀이 몇 분 만에 대회를 완주할 수 있는지 구하라.

입력

입력은 다음과 같이 주어진다.

N M L
a_1 b_1 d_1
...
a_N b_N d_N

출력

연세대학교 레이싱 팀이 몇 분 만에 대회를 완주할 수 있는지 출력한다.

제한

$1 \leq N \leq 1\,000$
$1 \leq M \leq 100$
$1 \leq L \leq 10^9$
$1 \leq b_i \leq a_i \leq 10^9$
$1 \leq d_i \leq 10^9$
$a_i - b_i$ 는 $d_i$ 의 배수이다.

예제5

예제 1
입력
```
2 2 10
8 4 4
16 1 15
```
예상 출력
```
3
```
예제 2
입력
```
3 4 5
4 2 2
12 6 3
2 1 1
```
예상 출력
```
2
```

예제 3

입력

2 100 1000000000
100 100 50
10000 1 9999

예상 출력

1000000000

예제 4
입력
```
2 10 500
10000 1 9999
100 100 50
```
예상 출력
```
1
```
예제 5
입력
```
1 100 1000000000
1 1 2
```
예상 출력
```
100000000000
```